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

💡문제

4613번 러시아 국기 같은 깃발

문제 링크

---

🤔접근법

범위 체크 및 시간복잡도 예상

• 1 ≤ N ≤ 50, 1 ≤ M ≤ 50
• $O(MN^3)$도 가능하다.

풀이법

⭕ 접근 방법. 완탐 + 누적합

1. 첫 번째 줄부터 i번 줄까지는 모두 흰색('W')으로 칠하고 이 부분을 toWhiteCnt에 저장 → $O(N)$
2. i 번째 줄 부터 j번째 줄까지 모두 파란색(’B’)로 칠하고 toBlueCnt에 저장 → $O(N)$
3. j 번째 줄 부터 마지막번째 줄까지 모두 파란색(’R')로 칠하고 toRedCnt에 저장 → $O(N)$

➡️ 해당 풀이법의 시간 복잡도 : $O(MN^3)$

---

😎SUCCESS

고냥 담박에 성공

---

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution_4613 {
    static int T; // 테스트 케이스의 수
    static int N; // 깃발의 행 수
    static int M; // 깃발의 열 수
    static char[][] board; // 깃발의 색 정보를 담은 2차원 배열
    static int min; // 새로 칠해야 하는 최소 칸의 개수

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
            min = Integer.MAX_VALUE;
            board = new char[N + 1][M];

            // 깃발의 색 정보 입력
            for (int i = 1; i <= N; i++) {
                board[i] = br.readLine().toCharArray();
            }

            int toWhiteCnt = 0; // 흰색으로 칠해져야 하는 칸의 개수
            int toBlueCnt; // 파란색으로 칠해져야 하는 칸의 개수
            int toRedCnt; // 빨간색으로 칠해져야 하는 칸의 개수

            // 첫 번째 줄부터 일정 부분까지는 흰색으로 칠해져야 함
            for (int i = 1; i <= N - 2; i++) {
                toWhiteCnt += toColor('W', i);
                toBlueCnt = 0;

                // 두 번째 줄부터 일정 부분까지는 파란색으로 칠해져야 함
                for (int j = i + 1; j <= N - 1; j++) {
                    toBlueCnt += toColor('B', j);
                    toRedCnt = 0;

                    // 나머지 부분은 빨간색으로 칠해져야 함
                    for (int k = j + 1; k <= N; k++) {
                        toRedCnt += toColor('R', k);
                    }

                    // 전체 칸의 최소 개수 갱신
                    min = Math.min(min, toWhiteCnt + toBlueCnt + toRedCnt);
                }
            }

            // 결과 출력
            sb.append("#" + t + " " + min + "\n");
        }
        System.out.println(sb.toString());
    }

    // 특정 행의 특정 색으로 칠해져 있지 않은 칸의 개수를 반환하는 메서드
    private static int toColor(char color, int r) {
        int cnt = 0;
        for (int c = 0; c < M; c++) {
            if (board[r][c] != color) cnt++;
        }
        return cnt;
    }
}