4613. 러시아 국기 같은 깃발

LEVEL D4

 

https://swexpertacademy.com/main/code/problem/problemSubmitHistory.do?contestProbId=AWQl9TIK8qoDFAXj

SW Expert Academy

 

아래 조건을 만족하는 러시아 국기 색을 만들면 된다.

• 위에서 몇 줄(한 줄 이상)은 모두 흰색으로 칠해져 있어야 한다.
• 다음 몇 줄(한 줄 이상)은 모두 파란색으로 칠해져 있어야 한다.
• 나머지 줄(한 줄 이상)은 모두 빨간색으로 칠해져 있어야 한다.

현재 상태를 입력 받으면서 각 W, B, R의 색상을 체크했다.

 

재귀를 통하여 현재 어떤 색으로 칠해왔는지를 판단하여 다음 칠할 색을 정하는 완전탐색을 진행했다.

 

흰색은 최대 N - 2까지 칠 할 수 있으며, 파란색은 최대 N -1 일때 까지 칠 할 수 있다.

 

#include<stdio.h>
#define WHITE 0
#define BLUE 1
#define RED 2
#define FINISH 3
const int maxAnswer = 0x7fffffff;
int map[50][3];
int N, M, answer = maxAnswer;
void solution(int start, int count, int sum, int color)
{
	if (color == FINISH) {
		for (int i = start; i < N; i++) {
			sum += (map[i][WHITE] + map[i][BLUE]);
		}
		if (sum < answer) {
			answer = sum;
		}
		return;
	}

	if (count == N) {
		if (color == FINISH && sum < answer) {
			answer = sum;
		}
		return;
	}

	if (color == WHITE) { 
		solution(start + 1, count + 1, sum + map[start][RED] + map[start][BLUE], BLUE);
	}
	else if (color == BLUE) {
		if (count < N - 2) {
			solution(start + 1, count + 1, sum + map[start][RED] + map[start][BLUE], BLUE);
		}
		if (count < N - 1) {
			solution(start + 1, count + 1, sum + map[start][WHITE] + map[start][RED], RED);
		}
	}
	else if (color == RED) {
		if (count < N - 1) {
			solution(start + 1, count + 1, sum + map[start][WHITE] + map[start][RED], RED);
		}
		solution(start + 1, count + 1, sum + map[start][WHITE] + map[start][BLUE], FINISH);
	}
	else if (color == FINISH) {
		solution(start + 1, count + 1, sum + map[start][WHITE] + map[start][BLUE], FINISH);
	}

}

int main()
{
	int tc = 1, T;
	scanf("%d", &T);
	for (tc; tc <= T; tc++) {
		answer = maxAnswer;
		scanf("%d %d", &N, &M);
		for (int i = 0; i < N; i++) {
			int w = 0, r = 0, b = 0;
			for (int j = 0; j < M; j++) {
				char ch;
				scanf(" %c", &ch);
				if (ch == 'W') {
					w++;
				}
				else if (ch == 'R') {
					r++;
				}
				else {
					b++;
				}
			}
			map[i][WHITE] = w;
			map[i][BLUE] = b;
			map[i][RED] = r;
		}

		solution(0, 0, 0, 0);
		printf("#%d %d\n", tc, answer);
	}
}