먼저 주어진 입력을 잘 처리하여 각 세로줄이 검은 줄('B'로 표기), 하얀 줄('W'로 표기), 모르는 줄('?'로 표기) 중 무엇인지를 구해두자. 이 과정에서 한 세로줄에 'B'와 'W'와 같이 있는 경우가 발견된다면 "UNDETERMINABLE"을 출력해주자.
그 뒤, 초기값으로 앞의 두 세로줄이 의미할 수 있는 문자열에 대한 상태를 저장하고, 세번째 세로줄부터 각 세로줄이 해당세로줄을 포함하는 크기 1 또는 2의 문자열로 구간을 나눌 수 있는지의 여부에 따라 DP를 진행해 문제를 해결해주자.
아래의 구현에서의 dp배열의 값은 "여러 경우가 존재함"을 의미하는 -1, "경우가 존재하지 않음"을 의미하는 0, "해당 세로줄이 그 한칸으로 기능하는 경우가 가능한 유일한 해석임"을 의미하는 1, "해당 세로줄이 그 전 세로줄과 이어 한칸으로 기능하는 경우가 가능한 유일한 해석임"을 의미하는 2로 구성되어있으니 코드를 읽을 때 참고하자. 여기에서 배열의 값인 1과 2는 dp의 해를 역추적하는 데에도 유용하게 사용할 수 있다.
예외적으로, '?'를 의미하는 세로줄 하나만이 입력이 들어왔을 경우의 답은 "0"임에 유의하자. '?'를 'B'로 해석해도 'W'로 해석해도 해당 문자열은 항상 "0"으로 동일하게 해석되기 때문이다. 이와 같이 복수의 해석이 가능하지만 그 모든 해석이 같은 문자열을 가리키는 경우는 이 경우가 유일하다. (증명은 간단하므로 생략한다.)
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
using namespace std;
int N;
string s[5];
bool chk = 1;
char arr[100];
int dp[100][2];
int cnt;
int idx, c;
vector<int> ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int r = 0; r < 5; r++) cin >> s[r];
for (int i = 0; i < N; i++) {
bool black = 0, white = 0;
for (int r = 0; r < 5; r++) {
if (s[r][i] == '.') white = 1;
else if (s[r][i] == 'X') black = 1;
}
if (black && white) chk = 0;
else if (black) arr[i] = 'B';
else if (white) arr[i] = 'W';
else arr[i] = '?';
}
if (!chk) {
cout << "UNDETERMINABLE";
return 0;
}
if (N == 1) {
cout << '0';
return 0;
}
if (arr[0] == 'B') dp[0][0] = 1;
else if (arr[0] == 'W') dp[0][1] = 1;
else dp[0][0] = dp[0][1] = 1;
if (arr[0] == 'B' && arr[1] == 'B') dp[1][0] = 2;
else if (arr[0] == 'B' && arr[1] == 'W') dp[1][1] = 1;
else if (arr[0] == 'B' && arr[1] == '?') dp[1][0] = 2, dp[1][1] = 1;
else if (arr[0] == 'W' && arr[1] == 'B') dp[1][0] = 1;
else if (arr[0] == 'W' && arr[1] == 'W') dp[1][1] = 2;
else if (arr[0] == 'W' && arr[1] == '?') dp[1][0] = 1, dp[1][1] = 2;
else if (arr[0] == '?' && arr[1] == 'B') dp[1][0] = -1;
else if (arr[0] == '?' && arr[1] == 'W') dp[1][1] = -1;
else dp[1][0] = -1, dp[1][1] = -1;
for (int i = 2; i < N; i++) {
if (dp[i - 2][1] && (arr[i - 1] == 'B' || arr[i - 1] == '?') && (arr[i] == 'B' || arr[i] == '?')) {
if (dp[i - 2][1] < 0 || dp[i][0]) dp[i][0] = -1;
else dp[i][0] = 2;
}
if (dp[i - 2][0] && (arr[i - 1] == 'W' || arr[i - 1] == '?') && (arr[i] == 'W' || arr[i] == '?')) {
if (dp[i - 2][0] < 0 || dp[i][1]) dp[i][1] = -1;
else dp[i][1] = 2;
}
if (dp[i - 1][1] && (arr[i] == 'B' || arr[i] == '?')) {
if (dp[i - 1][1] < 0 || dp[i][0]) dp[i][0] = -1;
else dp[i][0] = 1;
}
if (dp[i - 1][0] && (arr[i] == 'W' || arr[i] == '?')) {
if (dp[i - 1][0] < 0 || dp[i][1]) dp[i][1] = -1;
else dp[i][1] = 1;
}
}
if (dp[N - 1][0] == -1 || dp[N - 1][1] == -1 || (dp[N - 1][0] > 0 && dp[N - 1][1] > 0) || (dp[N - 1][0] == 0 && dp[N - 1][1] == 0)) {
cout << "UNDETERMINABLE";
return 0;
}
idx = N - 1;
if (dp[idx][1] > 0) c = 1;
while (idx > -1) {
ans.emplace_back(dp[idx][c] - 1);
idx -= dp[idx][c];
c ^= 1;
}
while (!ans.empty()) {
cout << ans.back();
ans.pop_back();
}
}
지문에 주어진 호텔의 각 방에 사람을 들이는 과정을 직접 시뮬레이션해 문제를 해결하자. 이는 아래의 구현의 chk변수와 같은 "현재 호텔에 빈 방이 있는지 여부를 표현하는 변수"와 조건문, 반복문 등을 이용해 구현할 수 있다.
입력으로 주어지는 N의 크기가 충분히 작으므로 시간 초과의 걱정은 하지 않아도 괜찮다.
아래는 제출한 소스코드이다.
#include <iostream>
using namespace std;
int N, G;
int arr[100];
int idx;
bool chk;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> G;
while (G--) {
int M; cin >> M;
while (M) {
if (chk) {
if (arr[idx] == 2) idx++;
else arr[idx++]++, M--;
}
else {
if (M == 1) arr[idx++] = 1, M--;
else arr[idx++] = 2, M -= 2;
if (idx == N) chk = 1, idx = 0;
}
}
}
for (int i = 0; i < N; i++) {
cout << arr[i] << '\n';
}
}