BOJ 11950

26 Mar 2020 • ProblemSolving

2016 IOI

문제출처

문제 해석

  • 러시아 국기를 만들기 위해 색을 칠해야하는 최소 수를 구하는 문제입니다.
  • 각 칸의 색을 임의의 색으로 바꿀 수 있습니다.
  • 전체 색을 바꿨을 때, 가장 위는 흰색, 가운데는 파란색, 아랫부분은 빨간색이어야 합니다.

설계(20)

  • W와 B를 어디까지 칠할지 선택(O(N^2))하면, 자동으로 빨간색은 칠할 위치가 정해지므로, 정해진 w와 b인덱스에 맞춰서 모든 공간을 돌며 바꿔야하는 색을 카운트 합니다(O(N^2)).
  • 총 시간복잡도는 O(N^4)으로 완전탐색으로 풀이가 가능합니다.
  • 모든 공간을 돌면서 바꿔야하는 색을 일일히 탐색하지않고, 미리 각 색의 누적합을 저장해놓아서 O(1)으로 최적화가 가능합니다. 따라서, 시간복잡도 O(N^2)에 해당 문제를 구현할 수 있습니다.

구현(40)

코드1(O(N^4))
#include <iostream>
using namespace std;

#define MAXN 50
#define INF 987654321

int N,M;
char map[MAXN][MAXN];
int ans=INF;
int main(){
    scanf("%d%d",&N,&M);
    for (int i = 0;i <N; i++){
        for (int j = 0; j < M; j++){
            scanf(" %1c",&map[i][j]);
        }
    }
    for (int w = 0; w < N-2; w++){
        for (int b = w+1; b < N-1; b++){
            int sum = 0;
            for (int i = 0;i <N; i++){
                for (int j =0;j<M; j++){
                    if (i >= 0 && i <= w){
                        if (map[i][j] != 'W') sum++;
                    }
                    else if (i > w && i <= b){
                        if (map[i][j] != 'B') sum++;
                    }
                    else{
                        if (map[i][j] != 'R') sum++;
                    }
                }
            }
            if (ans > sum) ans = sum;
        }
    }
    printf("%d\n",ans);
    return 0;

}
코드2(O(N^2))
#include <iostream>
using namespace std;

#define MAXN 50
#define INF 987654321

int N,M;
char map[MAXN][MAXN];
int num[MAXN][3];
int ans=INF;
int main(){
    scanf("%d%d",&N,&M);
    for (int i = 0;i <N; i++){
        for (int j = 0; j < M; j++){
            scanf(" %1c",&map[i][j]);
            if (map[i][j] =='W') num[i][0]++;
            if (map[i][j] == 'B') num[i][1]++;
            if (map[i][j] == 'R') num[i][2]++;
        }
    }
    for (int i = 1;i <N; i++){
        num[i][0] += num[i-1][0];
        num[i][1] += num[i-1][1];
        num[i][2] += num[i-1][2];
    }
    for (int w = 0; w < N-2; w++){
        for (int b = w+1; b < N-1; b++){

            int sum = num[w][1]+num[w][2];
            sum += num[b][0]+num[b][2] - (num[w][0] +num[w][2]);
            sum += num[N-1][0] + num[N-1][1] - (num[b][0] + num[b][1]);
            if (ans > sum) ans = sum;
        }
    }
    printf("%d\n",ans);
    return 0;

}
디버깅
cin >> N >> M;
for (int i = 0;i <N; i++){
    cin >> map[i];
}

scanf("%d%d",&N,&M);
for (int i = 0;i <N; i++){
    for (int j = 0; j < M; j++){
        scanf(" %1c",&map[i][j]);
    }
}
  • 처음에 위에서 보여지는 첫번째 방법으로 입력을 처리하였는데 WA가 나와서 원인을 찾는데 오래걸렸습니다.
  • 두번째 입력 방법으로 변경하니 맞게 처리가 되었습니다.
  • 문제에 따라서 첫번째방법이 허용이 되는 경우가 있고, 안되는 경우가 있는 것 같습니다. 이유는 알 수 없었습니다.
제출결과
  • 4ms(O(N^4)), 0ms(O(N^2))

마무리

  • 완전탐색문제였습니다. 입력방식에 따라 문제가 틀릴 수도 있다는 것을 알았습니다(이유가 불분명합니다).(X) => (추가)cin을 사용하는경우 “\0”이 들어갈 공간을 더 추가해주었어야 했습니다. (원인해결)
 BOJ  JOI2016

Related Posts