SW Expert 4613 JAVA : 러시아 국기 같은 깃발

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=3

SW Expert Academy

 

풀이 예상

W => B => R 순서가 무조건 유지 되어야 하기 때문에 시작 라인(0)은 흰색, 끝 라인(N)은 빨간색으로 칠해야 한다.

첫째줄에 흰색을 고정하고 나머지 숫자들 중 두개를 뽑아서 파란색 시작점과 빨간색 시작점을 뽑는다.

 

예를 들어 1,2,3,4 줄 이라면 2,3,4 중 두개를 뽑는다. 

그럼 경우의 수가 (2,3), (2,4), (3,4) 가 나온다.

입력을 받을 때 각 줄에 대해 색의 수를 2차원 배열에 저장해 두고 각 경우의 수 마다 계산해주면 된다! 

 

 

풀이방법 (접근 방법 & 시간복잡도)

시간 복잡도 => O(N^3)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static int N;
    static int M;
    static int answer = 0;
    static int[][] choice;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
 
            answer = Integer.MAX_VALUE;
            choice = new int[N][3]; //N,0 -> N번째 줄에서 W 만들때 필요한 개수, N,1-> B, N,2 -> R
            for (int n = 0; n < N; n++) {
                String str = br.readLine();
                int white = 0;
                int blue = 0;
                int red = 0;
                for (int i = 0; i < M; i++) {
                    int c = str.charAt(i);
                    if (c == 'W') white++;
                    if (c == 'B') blue++;
                    if (c == 'R') red++;
                }
                choice[n][0] = M-white;
                choice[n][1] = M-blue;
                choice[n][2] = M-red;
            }
 
            //여기서 1,2,3,...N-1중 2개를 골라야함.(B와 R이 시작하는 줄의 번호)
            for (int b = 1; b < N-1; b++) {
                for (int r = b+1; r < N; r++) {
                    //b -> Blue가 시작하는 줄의 번호, r -> Red가 시작하는 줄의 번호
 
                    int temp = 0;
                    //흰색 더해줌 -> 0줄 ~ b-1줄
                    for (int i = 0; i < b; i++) {
                        temp += choice[i][0];
                    }
                    //파란색 더해줌 -> b줄 ~ r-1줄
                    for (int i = b; i < r; i++) {
                        temp += choice[i][1];
                    }
                    //빨간색 더해줌 -> r줄 ~ N-1줄
                    for (int i = r; i < N; i++) {
                        temp += choice[i][2];
                    }
                    answer = Math.min(answer,temp);
 
                }
            }
 
            sb.append("#").append(t).append(" ").append(answer).append("\n");
        }
        System.out.println(sb);
 
    }
}

결과