📝 문제 정보#
문제 번역#
Mr. Dajuda는 TV 쇼 프로그램으로 유명한 사람으로, 가끔 시청자들에게 흥미로운 게임을 제안하고 상품을 상으로 제공합니다. 이번 주에 그가 제안한 게임은 다음과 같이 설명할 수 있습니다.
무대 위의 k개(k > 3)의 램프는 게임 시작 시 모두 꺼져 있습니다. 편의상 램프는 1부터 k까지 번호가 매겨져 있습니다. 각 램프는 빨간색 또는 파란색의 색상을 가지고 있습니다. 그러나 램프의 색상은 켜지기 전까지는 알 수 없습니다. 게임 참가자들은 무작위로 세 개의 램프를 선택하고 그 색상을 예측하도록 요청받습니다. 그런 다음 각 참가자는 선택한 램프의 예측된 색상이 기록된 종이를 게임 진행자인 Mr. Dajuda에게 제출합니다. 모든 램프가 켜지면 각 참가자는 자신이 예측한 색상 중 몇 개가 램프의 실제 색상과 일치하는지 확인합니다. 두 개 이상의 색상이 일치하면 상품을 받게 됩니다.
Mr. Dajuda는 오늘 특별한 선물을 준비했습니다. 게임 참가자들로부터 받은 모든 종이를 검토한 후, 가능하다면 모든 참가자가 상품을 받을 수 있도록 각 램프의 색상을 조정하려고 합니다.
위에서 설명한 대로 예측된 색상에 대한 정보가 주어졌을 때, 모든 참가자가 상품을 받을 수 있도록 모든 램프의 색상을 조정할 수 있는지 판단하는 프로그램을 작성하세요.
입력#
프로그램은 표준 입력에서 읽습니다. 입력은 두 개의 정수 k와 n (3 < k ≤ 5,000, 1 ≤ n ≤ 10,000)을 포함하는 줄로 시작하며, 여기서 k는 램프의 개수이고 n은 게임 참가자의 수입니다. 다음 n개의 각 줄에는 세 쌍의 (l, c)가 포함되어 있으며, 여기서 l은 선택한 램프 번호이고 c는 파란색의 경우 B, 빨간색의 경우 R인 문자로, 해당 램프에 대해 예측한 색상을 나타냅니다. l과 c 사이에는 공백이 있고, 각 (l, c) 쌍은 아래 샘플에 표시된 것처럼 공백으로 구분됩니다.
출력#
프로그램은 표준 출력에 씁니다. 모든 참가자가 상품을 받을 수 있도록 모든 색상을 조정할 수 있다면, 한 줄에 k개의 문자를 출력합니다. i번째 문자는 파란색의 경우 B, 빨간색의 경우 R로 i번째 램프의 색상을 나타냅니다. 불가능하면 -1을 출력합니다. 답이 여러 개 있는 경우 그 중 아무거나 출력할 수 있습니다.
🧐 관찰 및 접근#
- 2-sat 맛인거같은데, 3개중에 2개 이상을 맞게 해야한다…
- 다르게 말하면, $x1, x2, x3$ 3개가 있다고 할때
- $$ \begin{aligned} (\neg x1 \to x2 \land \neg x1 \to x3) \\ \lor \ (\neg x2 \to x1 \land \neg x2 \to x3) \\ \lor \ (\neg x3 \to x1 \land \neg x3 \to x2) \end{aligned} $$
- 와 같다.
- 그런데 2-sat으로 모델링하려면 or블럭들 사이가 and블럭으로 이어져 있어야하는데 반대다..
- 그런데, 3개중 2개가 참이어야 한다는 말은 어떤 두개를 골라도 모두 거짓일 수는 없다라는 말과 같다.
- 따라서 다음과 같이 훨씬 쉽게 모델링된다.
- $$(x_1 \lor x_2) \land (x_2 \lor x_3) \land (x_3 \lor x_1)$$
- 다르게 말하면, $x1, x2, x3$ 3개가 있다고 할때
💻 풀이#
- 코드 (C++):
void solve(){
int N, M; cin >> N >> M;
DirectedGraph graph(2*N);
rep(i, 0, M){
vector<int> args;
rep(j, 0, 3){
int idx; cin >> idx;
idx = (idx-1) * 2;
char c; cin >> c;
if(c == 'B') idx ^= 1; // R : 2k, B : 2k+1
args.push_back(idx);
}
rep(j, 0, 3) graph.add_2sat_edge(args[j], args[(j+1)%3]);
}
if(!graph.is2SAT()){
cout << -1;
return;
}
string ans = "";
rep(i, 0, N){
if(graph.sccId[2*i] < graph.sccId[2*i+1]) ans += 'R';
else ans += 'B';
}
cout << ans;
}