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

#. 문제 

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

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N,M(3≤N,M≤50)이 공백으로 구분되어 주어진다.

다음 N개의 줄에는 M개의 문자로 이루어진 문자열이 주어진다. i번 째 줄의 j번째 문자는 깃발에서 i번째 행 j번째 열인 칸의 색을 의미한다.

‘W’는 흰색, ‘B’는 파란색, ‘R’은 빨간색을 의미한다. ‘W’, ‘B’, ‘R’외의 다른 문자는 입력되지 않는다.

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 러시아 국기 같은 깃발을 만들기 위해서 새로 칠해야 하는 칸의 개수의 최솟값을 구하여 T 줄에 걸쳐서 출력한다.

#. 문제 이해

  - 첫 번째 행은 무조건 W, 마지막 행은 무조건 R.
    나머지 행은 겹칠 수 있는 색상 기준 새로 칠해야 하는 칸의 개수 최솟값을 비교하여 색상을 정해주어야 한다.

  - W, B, R 은 모두 최소 1행 이상 나와야 한다.

#. 풀이

  1.  각 행의 W, B, R 의 개수를 배열에 저장

         

  2. 최솟값을 구해야 하는 것은 결국 모든 경우의 수를 구해보아야 할 것임.

     그 중에서도 무조건 맨 위는 W, 맨 아래는 R 이 되어야 함.

     W가 나올 수 있는 행 경우의 수 1 ~ N-2 까지

     B가 나올 수 있는 행 경우의 수 2 ~ N-1 까지

     R가 나올 수 있는 행 경우의 수 3 ~ N 까지 

  

#. 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Solution4613 {
    static int[] W;
    static int[] B;
    static int[] R;
    static int N;
    static int M;
    
    public static void run() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int tc = Integer.parseInt(br.readLine());    // test_cast 입력
        
        for(int T=0; T<tc; T++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());  // line
            M = Integer.parseInt(st.nextToken());  // char
            
            W = new int[N];    // 각 행에서의 색상 개수
            B = new int[N];
            R = new int[N];
            
            // 1. 각 행의 W, B, R 개수 저장
            for(int i=0; i<N; i++) {    
                String flagRow = br.readLine();
                for(int j=0; j<M; j++) {
                    int word = flagRow.charAt(j);
                    if( word == 'W') W[i]++;
                    else if(word == 'B') B[i]++;
                    else R[i]++;
                }
            }
            
            // 2. 모든 경우의 수를 확인하여 최솟값 구하기
            int sum = 0;
            for(int i=1; i<=N-2; i++) {    // W가 나올 수 있는 경우의 수 : 1 ~ N-2  
                for(int j=i; j<N-1; j++) {    // W기준 B가 나올 수 있는 경우 : 2 ~ N-1
                    int wCnt = 0;
                    int bCnt = 0;
                    int rCnt = 0;
                    
                    for(int k=0; k<i; k++) wCnt += W[k];    // W가 나올 수 있는 행에서 W의 개수
                    for(int k=i; k<=j; k++) bCnt += B[k];    // W가 나올 수 있는 행에서 B의 개수
                    for(int k=j+1; k<N; k++) rCnt += R[k];    // W가 나올 수 있는 행에서 R의 개수
                    
                    sum = Math.max(sum, wCnt+bCnt+rCnt);    // sum이 높을 수록 새로 칠해야하는 칸의 개수가 작음
                }
            }
            sum = N * M - sum;
            bw.write("#" + (T+1) + " " + sum + "\n");
        }
        br.close();    
        bw.close();
    }
    
    public static void main(String[] args) throws Exception{
        Solution4613.run();
    }
}
 

#. 결과

  - Input --------------------------------------------------------

2

4 5

WRWRW

BWRWB

WRWRW

RWBWR

6 14

WWWWWWWWWWWWWW

WWRRWWBBBBBBWW

WRRRWWWBWWWWRB

WWBWBWWWBWRRRR

WBWBBWWWBBWRRW

WWWWWWWWWWWWWW

------------------------------------------------------------------

  - Output --------------------------------------------------------

#1 11

#2 44

------------------------------------------------------------------