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

문제링크

SW Expert Academy

Algorithm

Idea

가능한 모든 경우를 탐색한다. 가능한 기준선 i, j 경우의 수를 모두 탐색하며 W,B,R개수를 세서 cnt에 더해준다.

이를 반복하여 cnt 최댓값을 구하고 이를 전체에서 빼서 채워야하는 최소 개수를 구해준다.

---

Python

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    arr = [input() for _ in range(N)]

    mx = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            cnt = 0
            for s in range(i+1):
                cnt += arr[s].count('W')    # 하얀색 깃발 개수 count
            for s in range(i+1, j+1):
                cnt += arr[s].count('B')
            for s in range(j+1, N):
                cnt += arr[s].count('R')
            mx = max(mx, cnt)
    print(f'#{tc} {N*M-mx}')

Java

import java.io.*;
import java.util.*;

class Solution {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int test_case = 1; test_case <= T; test_case++) {
            String[] inputs = br.readLine().split(" ");
            int N = Integer.parseInt(inputs[0]);
            int M = Integer.parseInt(inputs[1]);
            
            String[] arr = new String[N];
            for (int i = 0; i < N; i++) {
                arr[i] = br.readLine();
            }
            
            int mx = 0;
            for (int i = 0; i < N - 2; i++) {
                for (int j = i + 1; j < N - 1; j++) {
                    int cnt = 0;
                    for (int s = 0; s <= i; s++) {
                        cnt += countColor(arr[s], 'W');
                    }
                    for (int s = i + 1; s <= j; s++) {
                        cnt += countColor(arr[s], 'B');
                    }
                    for (int s = j + 1; s < N; s++) {
                        cnt += countColor(arr[s], 'R');
                    }
                    mx = Math.max(mx, cnt);
                }
            }
            System.out.println("#" + test_case + " " + (N * M - mx));
        }
    }

    public static int countColor(String str, char color) {
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == color) count++;
        }
        return count;
    }
}