【백준】- 24912. 카드 색칠

문제

https://icpc.me/24912 

24912번: 카드 색칠

아이디어가 간결하면서도, 떠올리기 쉽지 않았던 것 같습니다. 복잡하게 생각할 수록 더 안 풀리는 문제였다고 생각해요...

 

풀이

문제에 조건에 의하면 처음부터 색칠되어 있는 카드가 있을 수 있습니다. 처음에 색칠되어 있는 카드 중 서로 같은 색으로 칠해진 인접한 카드가 있는 경우, 그리고 없는 경우로 나누어서 생각해 봅시다.

처음부터 같은 색으로 칠해진 인접한 카드가 있는 경우

이 경우는 항상 불가능합니다. 카드를 덧칠할 수 없고, 카드의 순서를 바꿀 수도 없기에, 이미 같은 색으로 칠해진 인접한 카드를 떼어놓을 방법이 없습니다.

입력에 처음부터 같은 색으로 칠해진 인접한 카드가 있다면, 항상 $-1$ 를 출력하면 됩니다.

 

처음부터 같은 색으로 칠해진 인접한 카드가 없는 경우

위의 경우와 반대로, 처음부터 같은 색으로 칠해진 인접한 카드가 없는 경우에는 항상 모든 카드를 문제의 조건을 만족하도록 칠할 수 있습니다.

색깔이 칠해지지 않은 카드를 하나 골라 칠하는 상황을 가정해 봅시다. 이 경우 양옆의 카드의 색이 어떤 색으로 칠해져 있는지 확인하고, 겹치지 않도록 칠해야 합니다.

주목하셔야 할 점은 카드를 칠할 수 있는 색의 가짓수는 $3$ 가지인데, 양옆의 카드의 색과 겹쳐서 칠할 수 없는 색깔의 가짓수는 아무리 많아봐야 $2$ 라는 점입니다. 그리고 오직 양옆에 칠해진 카드의 색만이 현재 칠하고자 하는 카드에 영향을 줄 수 있죠.

 

그렇기에 항상 양옆의 카드의 색과 관계없이 각각의 카드를 칠할 수 있게 됩니다. 이는 현재 칸에서 여러 종류의 색을 선택할 수 있어, 다음에 칠해야 하는 카드의 색상에 영향을 줄 때도 마찬가지로 작용합니다.

아래에 예시를 하나 준비해 두었으니, 혹시 이해가 여전히 안 되신다면 참고하시면 좋을 것 같아요!

결론

1. 처음부터 인접한 카드의 색이 같은 경우가 한 가지라도 있다면, 항상 불가능하므로 $-1$ 을 출력합니다.
2. 그렇지 않다면, 항상 카드의 색을 인접한 카드와 다르게 칠할 수 있습니다.
3. 카드를 배열로 생각하면, 배열의 처음부터 끝까지 순회하면서 인접한 카드의 색이 같은지를 확인하는 작업과 양옆의 카드의 색을 확인하고 그와 다른 색을 현재 카드에 칠하는 작업을 동시에 할 수 있습니다. 이 때의 시간복잡도는 $O(N)$ 이 됩니다.
4. 양옆의 카드의 색을 확인하는 작업과 달리, 인접한 카드의 색이 같은지를 확인하는 작업은 $i$ 번째 카드를 보고 있을 때 양옆의 카드 모두와 비교할 필요 없이 $i + 1$ 번째 카드와 비교하는 것으로 충분합니다. $i - 1$ 번째 카드를 보고 있을 때 $i$ 번째 카드와 같은지를 이미 비교했거나, $i$ 번째 카드의 색을 확인하고 $i - 1$ 번째 카드의 색을 다르게 칠했거나, 둘 중 하나임이 확실하니까요. 

코드

• C++17

#include <iostream>
using namespace std;

int cards[1000002];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int N;
    cin >> N;

    bool success = true;

    for (int i = 1; i <= N; i++) {
        cin >> cards[i];
    }

    for (int i = 1; i <= N; i++) {
        if (cards[i] == 0) {
            for (int j = 1; j <= 3; j++) {
                if (cards[i - 1] != j && cards[i + 1] != j) {
                    cards[i] = j;
                    break;
                }
            }
        } else {
            if (cards[i] == cards[i + 1]) {
                success = false;
                break;
            }
        }
    }

    if (success) {
        for (int i = 1; i <= N; i++) {
            cout << cards[i] << ' ';
        }
    } else {
        cout << -1;
    }
}

배열의 크기를 $1\;000\;002$ 로 잡은 것은 $1$ 번째, 또는 $N$ 번째 카드를 보고 있을 때 양옆의 카드를 확인하는 과정에서 배열의 범위를 초과하지 않도록 하기 위함입니다. 여러분의 코드에 예외 처리가 되어 있지 않다면, 조건문 등을 사용해서 배열의 범위를 초과하는 케이스도 고려해 주셔야 합니다.