[SWEA] 4613. 러시아 국기 같은 깃발

문제

2016년은 삼성전자가 러시아 현지법인을 설립한지 20주년이 된 해이다. 이를 기념해서 당신은 러시아 국기를 만들기로 했다.

먼저 창고에서 오래된 깃발을 꺼내왔다. 이 깃발은 N행 M열로 나뉘어 있고, 각 칸은 흰색, 파란색, 빨간색 중 하나로 칠해져 있다.

당신은 몇 개의 칸에 있는 색을 다시 칠해서 이 깃발을 러시아 국기처럼 만들려고 한다. 다음의 조건을 만족해야 한다.

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

이렇게 러시아 국기 같은 깃발을 만들기 위해서 새로 칠해야 하는 칸의 개수의 최솟값을 구하여라.

     

     

첫 번째 예제이다. 왼쪽에 있는 그림이 입력이다. 중간에 있는 그림에 X가 적힌 칸들을 새롭게 색칠하여 오른쪽에 있는 그림과 같은 깃발을 만들면 최적이다.

 

풀이방법

동적계획법(DP, Dynamic Programming) 알고리즘을 활용해 문제를 해결한다.

 

흰색, 파란색, 빨간색 중에서 유동적으로 변하지 않는 값(색을 새로 칠해야하는 칸의 수)을 찾는다.

 

흰색의 같은 경우 0번째 행에서 시작하므로 행을 1개, 2개, 3개 차지할 때 값이 변하지 않는다. 

 

빨간색의 경우도 마찬가지로 n-1번짹 행에서부터 칠해지므로 행을 1개, 2개, 3개 차지할 때 값이 유동적으로 변하지 않는다.

 

다만, 파란색의 경우 흰색의 행의 수에 따라 값이 유동적으로 변하게 된다.

 

파란색을 제외하고는 빨간색과 흰색은 여러 줄의 차지할 때 그 값이 고정이 된다.

 

따라서, 빨간색과 흰색이 각 각n, m줄일 때, 새로 칠해야하는 칸의 수를 미리 저장한다.

 

총 새로 칠해야하는 칸의 수는 흰색을  위에서부터 몇 줄 칠하고, 빨간색을 아래서부터 몇 줄 칠했을 때,

 

나머지 가운데 부분을 빨간색으로 칠했을 때 새로 칠하는 칸의 수를 구하면 된다.

 

이 때, 흰색의 몇줄, 빨간색의 몇줄은 미리 저장해서 알기 때문에, 파란색을 칠해야하는 수만 매 사이클마다 찾아주면 된다.

 

흰색과 빨간색이 1, 2, 3, ..., n-2행을 차지할 때의 값을 ws[m], rs[m]이라고 하고 파란색의 각 행을 새로 칠하는 수를 b[n]이라고 할 때,

 

총 새로 칠해야하는 칸의 개수는 ws[i] + rs[j] + r[i+1] + r[i+2] + ... + r[n-j]가 된다.

 

즉, 흰색을 i줄 칠하고, 빨간색을 j줄 칠했을 때, i+1부터 n-j줄까지는 파란색으로 칠하는 것이 된다.

 

소스코드

package samsung;

import java.util.*;

public class s_4613 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			char[][] a = new char[n][m];
			int[] w = new int[n];
			int[] b = new int[n];
			int[] r = new int[n];
			
			int[] ws = new int[n - 2];
			int[] rs = new int[n - 2];
			
			for(int i = 0; i < n; i++) {
				String s = sc.next();
				int w_cnt = 0;
				int b_cnt = 0;
				int r_cnt = 0;
				for(int j = 0; j < m; j++) {
					a[i][j] = s.charAt(j);
					if(a[i][j] != 'W') w_cnt++;
					if(a[i][j] != 'B') b_cnt++;
					if(a[i][j] != 'R') r_cnt++;
				}
				w[i] = w_cnt;
				b[i] = b_cnt;
				r[i] = r_cnt;
			}
			ws[0] = w[0];
			rs[0] = r[n-1];
			
			for(int i = 1; i < n - 2; i++) {
				ws[i] = ws[i - 1] + w[i];
				rs[i] = rs[i - 1] + r[n - 1 - i];
			}
			
			
			int result = n * m;
			for(int i = 0; i < n - 2; i++) {
				for(int j = 0; j < n - 2; j++) {
					int tmp = 0;
					tmp += ws[i];
					tmp += rs[j];
					for(int k = i + 1; k < n - j - 1; k++) {
						tmp += b[k];
					}
					result = Math.min(result, tmp);
				}
			}
			System.out.println("#" + t + " " + result);
		}
	}
}