2-SAT 문제의 가장 어려운 부분은 이 문제가 2-SAT 문제인지 알아내는 것 입니다. 문제에 전혀 힌트가 없기때문에, 처음부터 2-SAT를 고려하고 있지 않았다면 아예 방향을 잡지 못할수도 있습니다. 다행히도 백준의 문제들은 solved.ac와 연동을 통해 '태그'라는 기능을 제공하고 있기 때문에, 2-SAT 태그가 있는 문제를 풀면서 감을 익힐 수 있습니다. 이 글은 #2_sat 태그를 가지고 있는 문제들에 대한 풀이를 다룹니다.기본적으로 [백준 11281] 2-SAT - 4 를 풀 수 있을 정도의 지식이 있다고 가정하고 풀이를 작성했습니다. 문제는 티어 오름차순으로 정렬되어 있습니다.
[백준 7228] Melagiai
티어: 골3
문제 요약
선거에 출마한 N명의 후보자가 총 M개의 진술을 했습니다. 진술은 a b m 형태로 이루어져 있습니다.
m=0 이라면 a번째 후보는 b번째 후보가 진실만 말하는 '옳은 사람'이라고 진술한 것 입니다.
m=1 이라면 a번째 후보는 b번째 후보가 거짓말만 말하는 '나쁜 사람'이라고 진술한 것 입니다.
진술에서 모순이 없도록 N명의 후보자를 '옳은 사람', '나쁜 사람' 으로 정할 수 있다면 EGZISTUOJA를 출력하고, 그렇지 않다면 NEEGZISTUOJA를 출력하세요.
풀이
각 후보자를 boolean 변수로 설정하면, '옳은 사람'과 '나쁜 사람'을 각각 true와 false에 대응시킬 수 있습니다.
m=0일때,
a번째 후보가 '옳은 사람'이라면 진술이 진실이기 때문에, b번째 후보도 '옳은 사람' 입니다.
a번째 후보가 '나쁜 사람'이라면 진술이 거짓이기 때문에, b번째 후보도 '나쁜 사람' 입니다.
즉, m=0일때 a번째 후보와 b번째 후보는 같은 상태여야 합니다.
따라서 ~a or b와 a or ~b를 절로 추가해주면 됩니다.
m=1일때,
a번째 후보가 '옳은 사람'이라면 진술이 진실이기 때문에 b번째 후보는 '나쁜 사람' 입니다.
a번째 후보가 '나쁜 사람'이라면 진술이 거짓이기 때문에 b번째 후보는 '옳은 사람' 입니다.
즉, m=1일때 a번째 후보와 b번째 후보는 다른 상태여야 합니다.
따라서 a or b와 ~a or ~b를 절로 추가해주면 됩니다.
[백준 11280] 2-SAT - 3
티어: 플4
문제 요약
생략
풀이
생략
[백준 2207] 가위바위보
티어: 플4
문제 요약
학원에서 딴짓을 하다 총 n명의 학생들이 선생님에게 걸렸습니다. 선생님은 학생의 수가 너무 많아서, 새로운 방법으로 학생의 처벌 여부를 결정하려고 합니다. 그 방법은 바로, 선생님이 혼자서 총 m번의 가위바위보를 하고 이때 몇번째에 무엇을 냈는지 맞추면 그 학생을 처벌하지 않는 것입니다. 학생들은 선생님이 몇번째에 무엇을 낼 것 인지 총 2번 선택할 수 있고, 그중 1번 이상 맞추면 그 학생은 처벌 받지 않습니다. 그리고 오늘, 학생들은 선생님이 기분이 좋지 않아 보를 내지 않기로 했다는 정보를 입수했습니다. 학생들의 선택이 주어질 때, 모든 학생이 처벌 받지 않는 경우가 존재한다면 ^_^ 를 출력하고, 그렇지 않다면 OTL을 출력하세요.
풀이
스토리텔링이 잘 되어있지만, 결국 [BOJ 11280] 2-SAT - 3 문제와 똑같습니다. 각 학생이 적어도 2개의 선택중 1개는 맞춰야 하기 때문에, 이걸 or로 생각하면 각 선택을 절로 나타낼 수 있습니다.
[백준 3747] 완벽한 선거!
티어: 플4
문제 요약
선거에 출마한 N명의 후보자가 있습니다. 두 후보 i, j에 대해 여론조사를 해서, 다음 4가지 답변중 1개를 받았습니다.
i와 j중 적어도 1명은 당선되면 좋겠다. (입력 형식: +i +j)
i와 j중 적어도 1명은 떨어지면 좋겠다. (입력 형식: -i -j)
i가 붙거나, j가 떨어지거나, 둘 다 일어나면 좋겠다. (+i -j)
i가 떨어지거나, j가 붙거나, 둘 다 일어나면 좋겠다. (-i, +j)
이렇게 모인 M개의 답변을 동시에 만족하는 선거 결과가 있다면 1을 출력하고, 그렇지 않다면 0을 출력하세요.
(단, 모든 후보가 당선되거나, 모든 후보가 낙선하거나, 일부 후보만 당선되는 경우 모두 가능하다.)
풀이
각 후보자의 당선 여부를 boolean 변수로 설정합시다.
그럼 기존 2-SAT 문제와 똑같이 풀 수 있습니다. 각 답변을 하나의 절로 생각하면 됩니다.
여담으로, 각 입력값이 '공백' 으로 구분된다고 했기 때문에, 입력이 예제처럼 이쁘게 주어질거라고 생각하면 안됩니다.
'공백'에는 기존에 사용하는 한칸 공백 뿐만 아니라, 여러칸 공백, 줄바꿈, 여러번 줄바꿈까지 포함되어있기 때문입니다. 알아서 '공백'을 기준으로 토큰화해주는 C계열 언어가 아니라면 푸는데에 어려움이 있을 수 있습니다.
[백준 1217] 하우스 M.D.
티어: 플4
문제 요약
악명 높은 의사 하우스씨는 죽을 환자는 버리고, 살 환자는 살립니다. 이것을 판별하는 하우스씨의 특별한 표가 있습니다. 그 표는 바로, 관리하는 환자들 중, 어떤 증세 2개가 동시에 관측되면 그 환자는 죽게된다는 규칙을 정리한 표입니다. 예를 들어 뇌출혈이 일어나지 않는 상태와 불면증인 상태가 동시에 관측되면 그 환자는 죽게된다는 규칙이 있을 수 있죠. 그런데 최근들어 의사 하우스씨 손에 맡겨진 환자가 너무 많이 죽어나가는 바람에, 하우스씨의 규칙이 담긴 표가 너무 가혹해서 살아남을 수 있는 환자가 없는게 아닐지 검사해볼 필요가 생겼습니다. 하우스씨의 규칙이 주어졌을 때, 살아남을 수 있는 환자가 있다면 1을 출력하고, 그렇지 않다면 0을 출력하세요.
풀이
두 조건을 모두 만족하면 환자는 죽습니다. 환자가 살아남기 위해선, 두 조건을 모두 만족해서는 안된다는 뜻이 됩니다. 조건의 만족 여부를 boolean 변수로 설정하면, 두 조건 a,b에 대해 !(a and b) = true 여야 살아남을 수 있다는걸로 해석할 수 있습니다. 이는 ~a or ~b 와 동치입니다. 따라서 ~a or ~b를 절로 추가해주면 됩니다.
[백준 13744] Illumination
티어: 플4
문제 요약
유령이 나온다고 알려진 n*n 정사각형 격자 모양의 집을 상속받았습니다. l개의 램프가 고정된 위치에 있고, 각 램프는 자신의 행 또는 열 중에 하나만 비출 수 있습니다. 램프의 조명은 양쪽 방향으로 r칸 만큼 뻗어나갈 수 있습니다. 따라서 집 외벽에 막히지 않는 램프는 최대 2r+1칸을 비출 수 있습니다.
만약, 어떤 칸이 같은 행의 두 개 이상의 램프에 의해 비춰지거나, 같은 열의 두 개 이상의 램프에 의해 비춰지면 그 칸은 너무 밝아서 유령이 도망갈 것 입니다. (어떤 칸이 행 방향 램프 하나와 열 방향 램프 하나로 비춰지는것은 괜찮습니다.) 당신은 유령을 쫓아내지 않고 모든 램프를 켜고 싶습니다. n, r, l과 램프들의 위치가 주어질 때, 유령을 쫓아내지 않고 모든 램프를 켜는것이 가능하다면 1을 출력하고, 그렇지 않다면 0을 출력하세요.
풀이
목표는 유령을 쫓아내지 않는 것 입니다. 유령을 쫓아내려면,
1. 같은 행이나 열에 있고,
2. 두 램프 사이 거리가 2*r 이하인 경우에
3. 두 램프 모두 그 행 또는 열 방향으로 켜야합니다.
1, 2번은 입력에 따라 결정됩니다. 그럼 유령을 쫓아내지 않기 위해선 1, 2번 조건을 만족하는 경우의 두 램프가 그 행 또는 열 방향으로 켜지지 않게 해야합니다. 여기서 행, 열을 true와 false로 놓고 2-SAT 처럼 풀 수 있습니다. 각 램프를 indexing 해서 하나의 숫자로 표현되도록 한 뒤, 모든 램프 쌍에 대해 1, 2번 조건을 만족하는지 확인하고, 만약 만족한다면 두 램프 a, b에 대해 같은 행인 경우 ~a or ~b, 같은 열인 경우 a or b 로 절을 추가해주면 됩니다. l이 충분히 작기 때문에 모든 램프 쌍에 대해 n^2 완전 탐색을 해줄 수 있습니다.
[백준 11281] 2-SAT - 4
티어: 플3
문제 요약
생략
풀이
생략
[백준 3648] 아이돌
티어: 플3
문제 요약
상근이는 아이돌 오디션에 참가했습니다. n명의 참가자중 상근이는 1번입니다.
m명의 심사위원은 1명이 총 2개의 표를 행사할 수 있으며, 임의의 참가자를 찬성하거나 반대할 수 있습니다. i번 참가자에 찬성하면 i, 반대하면 -i로 입력이 주어집니다.
각 심사위원은 자신의 두 표중 적어도 한 표는 결과에 영향을 끼쳐야한다고 생각합니다. 예를들어 고원섭 심사위원이 i, -j로 표를 행사했다고 합시다. 이경우 i번 참가자에 찬성, j번 참가자에 반대했다는것을 의미합니다. 만약 결과로 i번 참가자는 떨어지고, j번 참가자는 합격했다면 고원섭 심사위원은 투표의 공정성에 대해 의심하게 됩니다.
상근이는 심사위원의 의심을 받지 않으면서 투표 내용을 조작해서, 다음 라운드에 진출하는 목록을 만들 수 있는지 알고 싶습니다. 물론, 상근이도 다음 라운드에 꼭 진출해야합니다. 상근이를 포함한 다음 라운드 진출자 목록을 심사위원의 의심을 받지 않고 만들 수 있다면 yes를 출력하고, 그렇지 않다면 no를 출력하세요.
풀이
적어도 둘 중 하나는 투표결과로 반영되어야하기 때문에, 2-SAT의 개념을 생각해보면 심사위원마다 던진 표들을 절로 생각하면 된다는걸 알 수 있습니다. 마침 입력도 찬성이 x, 반대가 -x이기 때문이죠. 하지만 여기서 중요한건, 상근이는 다음 라운드에 꼭 진출해야 한다는 것 입니다. 즉, 의심없이 다음 라운드 진출자 목록을 만들어도 거기에 상근이가 없다면 실패인것이죠. 따라서 기존 입력에 1 or 1 절을 추가해주어야합니다. x or x 가 true가 되려면 x가 true인 방법밖에 없기 때문입니다.
[백준 2416] 문
티어: 플3
문제 요약
두 저수지 사이에 n개의 수로가 있습니다. 수로에는 2개의 문이 있으며, 수로의 문을 제어하는 m개의 스위치도 있습니다. 스위치가 켜졌는지 꺼졌는지에 따라 수로가 닫히고 열리는건 수로마다 다릅니다. 어떤 문은 스위치가 켜졌을때 닫혀있고, 어떤 문은 스위치가 꺼졌을때 닫혀있기 때문입니다. 수로에 있는 2개의 문 중에 1개라도 닫혀있다면 그 수로는 닫혀있다고 할 수 있습니다. 각 수로의 정보는 a, s_a, b, s_b 로 주어지며 s_i = 0 일때 i번째 스위치가 꺼져있어야 문이 닫히는것이고, s_i = 1 일때 i번째 스위치가 켜져있어야 문이 닫히는것입니다. 모든 수로를 닫는것이 가능하다면 수로를 닫는 m개의 스위치의 상태를 출력하고, 불가능하다면 IMPOSSIBLE을 출력하세요.
풀이
모든 수로가 닫혀야합니다. 그렇기 위해선, 수로에 있는 2개의 문 중에 적어도 1개는 닫혀있어야합니다. 이 문을 조절하는 2개의 스위치에 대해, 문이 닫히게 만드는 스위치의 상태를 a, b라고 합시다. 이 상태를 boolean 변수로 나타내어 2-SAT으로 풀 수 있습니다. 스위치가 켜져있어야 문이 닫히는경우 true, 꺼져있어야 문이 닫히는경우 false로 결정하면 각 수로에 대해 수로를 닫혀있게 만들기 위해 a or b 라는 절을 만들 수 있습니다. 구체적으로, s_i가 0인 경우 - 를 붙여주면 원래 2-SAT와 다를바 없는 문제가 됩니다. 예를 들어 수로의 정보가 3 0 2 1 로 들어왔으면, 실제로 2-SAT에 절로 들어가는 식은 -3 or 2 가 됩니다. 3번 스위치가 -3(즉, 꺼진상태)가 false이고 2번 스위치가 2(즉, 켜진상태)가 false이면 안된다고 해석할 수 있습니다.
[백준 16915] 호텔 관리
티어: 플3
문제 요약
호텔에는 총 n개의 방이 있고, 방의 잠금장치를 제어할 수 있는 m개의 스위치도 있습니다. 모든 방은 2개의 스위치와 연결되어 있습니다. 하지만, 하나의 스위치에 여러개의 방이 연결되어있거나 아예 연결이 되지 않았을수도 있습니다. 스위치를 누르면, 연결된 모든 방의 잠금 상태가 반전됩니다. 잠겨있는 방은 열리고, 열린 방은 잠깁니다. 초기 방의 잠금 상태와, 스위치와 연결된 방의 정보가 주어질 때 모든 방을 열 수 있는지 판단하세요. 모든 방을 열 수 있다면 1을 출력하고, 그렇지 않다면 0을 출력하세요.
풀이
스위치의 사용 여부를 boolean 변수로 관리하면 됩니다. 방에 연결된 스위치가 a, b라고 가정합시다.
닫혀있는 방은 연결된 2개의 스위치중 단 1개만 사용해야합니다. 즉 a or b와 ~a or ~b를 절로 추가하면 됩니다.
열려있는 방은 연결된 2개의 스위치를 모두 사용하거나, 사용하지 않아도 됩니다. 두 스위치의 사용 여부가 같기만 하면 됩니다.
즉 ~a or b와 a or ~b를 절로 추가하면 됩니다.
[백준 16367] TV Show Game
티어: 플2
문제 요약
TV Show에서 간단한 게임을 진행합니다. 무대 위 k개의 조명은 모두 꺼진 상태이며, 모든 조명은 각각 빨간색과 파란색중 하나의 색을 가지고 있습니다. 하지만 조명이 켜지기 전까지는 색깔을 알 수 없습니다. n명의 게임 참가자들은 k개의 조명중 3개의 조명을 선택해서, 어떤 색깔일지 예측한 답변을 제출합니다. 만약 답변한 3개의 조명중 2개 이상이 답변과 일치한다면 선물을 받게 됩니다.
TV Show의 주최자는 오늘 특별한 선물을 준비했기 때문에, 모든 게임 참가자가 선물을 받았으면 좋겠습니다. 그래서 게임 참가자들에게 답변을 미리 받은 후, 가능하다면 모든 참가자가 선물을 받을 수 있도록 조명 색을 조정하려고 합니다.
게임 참가자들의 답변이 주어졌을 때, 모든 참가자가 선물을 받을 수 있도록 조명 색을 조정할 수 있다면 첫번째 줄에 k개의 문자를 출력하세요. i번째 문자가 R 이라면 i번째 조명이 빨간색임을 나타내고, i번째 문자가 B라면 i번째 조명이 파란색임을 나타냅니다. 만약 그렇지 않다면, -1을 출력하세요.
풀이
참가자가 선물을 받는 유일한 조건은, 답변한 3개의 조명중 2개 이상이 답변과 일치해야한다는 것 입니다. 이걸 조건으로 어떻게 나타낼 수 있을까요?
만약 답변한 3개의 조명중 하나가 틀렸다고 가정하면, 선물을 받기 위해선 나머지 두개의 조명을 예측한게 무조건 맞아야 합니다.
예측한 조명을 a,b,c라고 했을때 ~a -> b,c 라는 명제를 만들 수 있게 됩니다. 물론 ~b -> a,c와 ~c -> a,b 도 있습니다.
여기서 ~a -> b 와 ~b -> a에 주목해봅시다. 이 두개를 합친것과 같은 논리식이 a or b 라는것을 알 수 있습니다. ~a -> b 에서는 a가 false일 때 b가 true여야 한다는것을 나타내고, ~b -> a는 b가 false 일때 a가 true여야 한다는걸 나타내기 때문입니다. a와 b모두 true여도 상관은 없습니다. 하지만 둘다 false일 수는 없겠죠.
따라서 ~a -> b, ~a -> c, ~b -> a, ~b -> c, ~c -> a, ~c -> b 라는 6개의 명제를 a or b, b or c, c or a 라는 3개의 논리식으로 나타낼 수 있게 됩니다.
이제, 조명이 빨간색인 경우를 true, 파란색인 경우를 false로 하고 2-SAT 으로 풀면 됩니다. 각 참가자의 답변 3개는 a or b, b or c, c or a 라는 3개의 절로 나타내어지기 때문이죠.
만약 만들 수 있다면 true, false를 다시 R, B에 대응시켜 출력해주면 됩니다.
[백준 4230] 사랑과 전쟁
티어: 플2
문제 요약
철승이와 그의 아내 보람이는 n쌍의 부부가 모이는 파티에 참가했습니다. 파티장에는 긴 테이블이 있고, 양쪽으로 n개의 의자가 마주보고 있습니다. 이 파티에는 부부끼리는 서로 같은 방향의 의자에 앉으면 안된다는 규칙이 있었기 때문에, 철승이와 보람이는 서로 양쪽 첫번째 줄 의자에 앉았습니다. 그런데 다른 사람의 귀뜸으로, 철승이는 이 파티에 m쌍의 불륜 커플이 있다는것을 알았습니다. 이런 불륜 커플들을 순수한 보람이에게 보여주지 않기 위해, 불륜 커플끼리는 철승이가 앉은 줄에 같이 앉지 못하게 사람들의 자리를 정해주려고 합니다. 조건을 만족하도록 사람들을 앉힐 수 있다면, 보람이쪽 의자에 앉아야 하는 사람들의 번호를 출력하세요. 그렇지 않다면, bad luck을 출력하세요.
(문제에는 제시되어있지 않지만, 철승이와 보람이도 불륜 커플이 있을 수 있습니다. 즉, 입력으로 0h, 0w가 주어질 수도 있습니다.
또한, 각 부부는 서로 이성이지만 불륜 커플은 동성간에도 일어날 수 있습니다.)
풀이
보람이 줄에 앉았는지 여부를 boolean 변수로 놓으면 됩니다.
우선 부부끼리는 같은 줄에 앉을 수 없기때문에 각 부부의 남편과 아내 h, w에 대해 h or w, ~h or ~w 절을 추가해주면 됩니다.
불륜 커플은 둘 모두 철승이 줄에 앉으면 안됩니다. 즉, 둘 모두 false 일수는 없다고 해석할 수 있습니다. 따라서 불륜 커플 a, b에 대해 a or b절을 추가해주면 됩니다.
출력은 true인 변수만 오름차순으로 해주면 됩니다.
철승이는 사실 본인도 불륜을 하고 있었고, 순수한 보람이는 사실 순수하지 않습니다. 이게 사랑과 전쟁 아닐까요?
[백준 30879] 저녁 뭐 먹지?
티어: 플2
문제 요약
선아와 친구들은 저녁을 뭘로 먹을지 고민하고 있습니다. 이건 매우 중대한 고민이기 때문에, 이를 해결하기 위해 선아를 포함한 n명의 친구들은 다음과 같이 행동하기로 했습니다.
1 a b: 저녁메뉴에 대한 의견을 나타내는 두 정수 a, b를 제시합니다. 정수가 양수이면 그 특징이 저녁메뉴에 있어야 한다는 뜻이고, 정수가 음수이면 그 특징이 저녁메뉴에 있으면 안된다는 뜻 입니다.
2: 현재까지 의견을 제시한 친구들의 의견을 바탕으로, 각각의 친구가 제시한 2개의 의견중에 최소 1개는 반영되는 저녁메뉴가 있는지 없는지 알려줍니다.
2번 행동이 입력으로 들어올 때 마다, 조건에 맞는 저녁메뉴가 있다면 YES DINNER을 출력하세요. 그렇지 않다면, NO DINNER을 출력하세요.
풀이
가장 처음으로 해야하는 관찰은, 한번 NO DINNER이 되었다면 그 이후에는 어떠한 경우에도 항상 2번 행동의 답은 NO DINNER이라는 것 입니다. 문제 자체는 단순히 a,b 자체가 양수/음수로 예쁘게 들어오기 때문에 고민하지 않고 a or b 절을 추가해도 되지만, n 제한이 200,000이기 때문에 모든 2번 쿼리마다 2-SAT을 돌리면 n^2과 비슷한 시간복잡도로 시간 초과를 받고 말 것 입니다.
그럼 2번 쿼리마다 2-SAT을 돌리다가, 한번 NO DINNER이 나왔다면 그 이후로는 2-SAT을 안쓰면 해결되는 것 일까요? 아닙니다!
입력이 끝날때까지 YES DINNER이 유지된다면, 결국은 n^2 시간복잡도로 풀 수 없게 되고맙니다.
앞에서 했던 관찰을 달리 말하면, 어떤 i번째 쿼리까지 처리했을 때 결과가 YES DINNER 이라면 i보다 작은 모든 쿼리에 대해 YES DINNER이 답으로 나온다는 것 입니다. 결국 출력은, YES DINNER에서 NO DINNER로 바뀌는 단 1개의 구간을 제외하고는 항상 단조성을 띄게 됩니다.
따라서 YES DINNER에서 NO DINNER로 바뀌는 k번째 쿼리를 이분 탐색으로 찾아준다면, 각 쿼리에 대해 k와의 대소 관계로 답을 구할 수 있게 됩니다.
[백준 6937] Coke or Chocolate Milk
티어: 플2
문제 요약
파티에 참가한 아이들에게 각각 콜라와 초콜릿 우유중 하나를 주려고 합니다. 아이들은 각자 요청사항이 있습니다. 뭐, 예를 들면 "저도 OO이랑 같은거 마실래요!" 라던가요.. 더 정확히 말하면, 아이들은 5가지 형식중에 하나로 요청사항을 말합니다.
- <person1> wants <drink1> : 사람1은 음료1을 마시고 싶어요
- <person1> hates <drink1> : 사람1은 음료1을 마시기 싫어요
- <person1> want same as <person2> : 사람1은 사람2와 같은걸 마시고 싶어요
- <person1> want different from <person2> : 사람1은 사람2와 다른걸 마시고 싶어요
- <person1> want <drink1> if <person2> gets <drink2> : 만약 사람2가 음료2를 마신다면, 사람1은 음료1을 마시고 싶어요
<person>은 20글자 이내의 영어 소문자로 이루어져있고, <drink>는 콜라와 초콜릿 우유중 하나입니다.
모든 아이를 만족시킬 수 있다면 각 아이가 받는 음료를 출력하세요. 그렇지 않다면, Everybody gets water를 출력하세요.
콜라와 초콜릿 우유중 어떤것도 상관없는 아이에겐 콜라를 주고, 가능한 경우가 여러개라면 사전순으로 앞선 사람부터 배정해 출력하세요.
(예제 입력만 보고 헷갈리기 쉬운데, 테스트케이스가 여러개일 수 있습니다. 입력의 끝에는 0이 주어진다고 명시되어있습니다.)
풀이
각각의 아이가 콜라와 초콜릿 우유중 어느것을 골랐는지를 boolean 변수로 관리하고, 각 요청사항에 대해 알맞게 적용하면 됩니다. 가장 까다로운 부분은 5번째 형식의 요청사항만 예시로 들어보겠습니다. 조건을 두부분으로 나눠 사람2가 음료2를 마시는지 여부 = P, 사람1이 음료1을 마시는지 여부를 Q라고 할 때 P -> Q 라는 조건이 되고, 이는 ~p or q 와 동치입니다. 이제 음료1과 음료2가 가질 수 있는 경우의 수 4가지 (콜라,초콜릿 우유), (콜라, 콜라), (초콜릿 우유, 콜라), (초콜릿 우유, 초콜릿 우유)에 대해 알맞은 형태로 절을 만들어 추가해주면 됩니다.
들어오는 입력을 처리하기가 까다롭고 세세한 조건이 많아서 구현이 힘들 수 있습니다.
[백준 15675] 괴도 강산
티어: 플1
문제 요약
n행 m열의 격자 모양 박물관에 괴도 강산이 예고장을 보냈습니다. 박물관 관장인 택희는 이를 막기 위해, 보석이 없는 빈 칸중 일부에 위치추적기를 설치했습니다. 만일 강산이 위치추적기를 가져간다면 강산은 잡히고 말것입니다.. 하지만 강산은 위치추적기가 설치되어있다는 정보를 알아차리고, 아래와 같은 전략을 사용하기로 했습니다.
1. 행과 열중 하나를 선택해서 고른 행(열) 전체를 왼쪽(위쪽)에서 오른쪽(아래쪽)까지 지나가면서 다음과 같은 행동을 한다.
i. 보석/위치추적기가 있는 칸을 지나면 그것을 반드시 가져온다.
ii. 현재 위치추적기를 가지고 있으며, 위치추적기가 있었지만 지금은 비어있는 칸을 지난다면 그 위치에 위치추적기 1개를 버린다.
2. 모든 보석을 얻었고, 가지고 있는 위치추적기가 0개라면 박물관을 떠난다. 그렇지 않다면, 1번의 작업을 반복한다.
하지만 만만치 않은 택희는 이것을 알아차리고, 보석이 사라지면 즉시 그 자리에 경비원을 출동시킬 것 입니다. 이로 인해 강산은 다시는 그 칸을 포함한 행과 열을 선택하지 못합니다. 예를 들어 위치가 (i,j)인 보석을 강산이 훔치면, 그 이후에 강산은 i행과 j열을 선택할 수 없습니다. 강산이가 모든 보석을 얻었으며, 가지고 있는 위치추적기가 0개인 상태로 박물관을 떠날 수 있다면 1을 출력하세요. 그렇지 않다면, 0을 출력하세요.
풀이
각 칸에서 행/열을 선택했는지 여부를 boolean 변수로 관리해야한다고 생각할 수 있지만, 임의의 행과 열에 대해 그 칸이 유일하게 결정되기 때문에 그냥 각 행/열을 선택했는지 자체의 여부를 boolean 변수로 관리해주면 됩니다. 0~n-1까지를 행에 대응시키고, n+1부터 n+m까지를 열에 대응시키는것이 하나의 방법이 될 수 있습니다. 어떤 칸 (i,j)가 위치추적기라면 i행과 j열을 아예 방문하지 않거나, i행을 방문하면서 위치추적기를 가져가고, j열을 방문해서 다시 위치추적기를 놔두는 방법이 있을 수 있습니다. 즉, i행 == j열 이여야합니다. 따라서 ~i or j와 i or ~j 절을 추가해주면 됩니다. 마찬가지로 어떤 칸 (i,j)가 보석이라면 i행만 방문하거나, j열만 방문해야합니다. 즉, i xor j가 true여야합니다. 따라서 i or j 와 ~i or ~j 절을 추가해주면 됩니다.
[백준 13166] 범죄 파티
티어: 플1
문제 요약
n명의 용의자가 있습니다. 각 용의자에겐 친구가 2명씩 존재합니다. 친구들은 여러 용의자의 친구가 될 수 있지만, 최대 2명의 용의자와만 친구일 수 있습니다. 용의자는 자신이 범인이 아닌걸 증명하기 위해, 자신의 친구에게 거짓 알리바이를 부탁합니다. 친구가 거짓 알리바이를 수락하면, 그 친구는 변호인이 됩니다. 하지만 거짓 알리바이를 말하는걸 다들 꺼려하기 때문에, 용의자들은 친구에게 성의를 보여야합니다. 그래서 용의자들은 파티를 열기로 했습니다. 친구들마다 변호인이 되는 성의의 임계값이 존재하며, 파티의 비용이 임계값 이상이면 그 친구는 용의자의 변호인이 됩니다. 모든 용의자가 최소 1명 이상의 변호인을 가지도록 하는 파티 비용이 존재한다면, 파티 비용의 최솟값 k를 출력하세요. 그렇지 않다면, -1을 출력하세요.
풀이
용의자가 가진 친구도 2명이고, 한 친구와 친한 용의자는 최대 2명이라는것에서 2-SAT으로 푸는 힌트를 얻을 수 있습니다. 용의자-친구 관계를 boolean 변수로 놓아봅시다. 그 친구가 이 용의자의 변호인이라면 true가 될것입니다. 용의자는 최소 1명의 변호인을 가져야하고, 2명을 가져도 상관없기 때문에 용의자에 대한 친구 관계 a,b에서 a or b 라는 절을 만들 수 있습니다.
하지만 친구는 동시에 두명을 변호할 수 없기 때문에, 친구에 대한 용의자 관계 c, d에서 ~c or ~d 라는 절을 추가로 만들 수 있습니다. 이로써 c와 d 둘다 true일수는 없습니다.
마지막으로, 최솟값은 항상 친구들이 가지고 있는 임계값중에 1개일 것입니다. 그리고, 임의의 용의자의 친구 2명의 임계값 x, y에 대해 파티 비용 k가 k < min(x,y)를 만족하면 그 용의자는 변호인을 가질 수 없으므로 바로 불가능하단걸 알 수 있게 됩니다. 각 임계값 쌍 min(x_i,y_i)들의 최댓값이 min값이 되고, k는 임계값들에서 이분탐색을 돌리되, k < min 인 경우를 스킵함으로써 시간을 아끼면 시간제한 안쪽으로 통과할 수 있습니다.
[백준 1739] 도로 정비하기
티어: 플1
문제 요약
가로 n개, 세로 m개의 도로가 있는 도시가 있습니다. 도로가 너무 복잡하기 때문에, 이 도시의 시장은 각 도로마다 방향을 정해서, 그 방향으로만 이동할 수 있게 만들려고 합니다. 하지만 그렇게 되면 시민들의 반발이 클 것이기 때문에, 동시에 이 도시에서 버스를 운행하려고 합니다. 정확히는, a번째 가로 도로와 b번째 세로 도로가 만나는 지점 (a,b)가 시작점이고, c번째 가로 도로와 d번째 세로 도로가 만다는 지점 (c,d)가 도착점인 버스를 k개 운행하려고 합니다. 버스가 많기때문에 각 버스는 시작점에서 많아야 가로 도로 1개와 세로 도로 1개만을 이용해서 도착점에 도달하고 싶습니다. k개의 버스의 시작점과 도착점이 주어졌을 때, 모든 버스가 조건을 만족하며 운행할 수 있도록 도로 방향을 정할 수 있을까요? 만약 도로 방향을 조건에 맞게 정할 수 있다면 Yes를 출력하세요. 그렇지 않다면, No를 출력하세요.
(시작점과 도착점이 같을수도 있습니다.)
풀이
가로 n개와 세로 m개의 도로를 boolean 변수로 놓으면 됩니다. 이 풀이에선 좌->우 방향 (위->아래 방향)이 true라고 놓고 설명합니다. 만약 a==c 이고 b==d 라면, 시작점과 도착점이 같으므로 조건이 필요없습니다.
그렇지 않다면, 각 도로의 방향이 어떻게 정해져야하는지 생각해봅시다. 편의상 가로/세로 수식어는 생략하고 a,b,c,d 도로라고 부르겠습니다. 우선 문제의 조건에서, 시작점부터 도착점까지 가로 도로 1개와 세로 도로 1개만을 이용할 수 있다고 했습니다. 이건 결국 아래 2가지 경우 중 1개입니다.
1. (a,b)에서 (a,d)까지 a도로로 이동한 뒤에 (a,d)에서 (c,d)까지 d도로로 이동한다.
2. (a,b)에서 (c,b)까지 b도로로 이동한 뒤에 (c,b)에서 (c,d)까지 c도로로 이동한다.
결국 이 두가지 경우를 논리식으로 나타내보면 (a and d) or (b and c) 가 됩니다. 원래 2-SAT에서 쓰이는 형식인 (x or y) and (z or w) 와는 다릅니다. 따라서 이를 바꿔줄 필요가 있습니다. 먼저 분배법칙을 사용해서 (a or (b and c)) and (d or (b and c)) 로 쓸 수 있고, 한번 더 분배법칙을 사용하면 (a or b) and (a or c) and (d or b) and (d or c)가 됩니다. 이제 사용할 수 있습니다!
처음에 각 도로는 boolean 변수로 놓을 때, 사용 여부가 아니라 방향을 기준으로 boolean 값을 정했습니다. 따라서 방향을 고려할 조건식이 추가로 필요합니다. 간단하게 아래와 같이 발상해볼 수 있습니다.
- a의 boolean 값은 b < d 의 boolean 값과 같습니다. b가 b보다 작다면 시작점에서 도착점으로 가기 위해서는 오른쪽으로 이동해야하기 때문입니다.
- c의 boolean 값은 a의 boolean 값과 같습니다. 이유는 같습니다.
- b의 boolean 값은 a < c 의 boolean 값과 같습니다.
- d의 boolean 값은 b의 boolean 값과 같습니다.
이 모든 처리를 끝낸 뒤에, 마지막으로 체크해야할 부분은 a==c 이거나 b==d 인 경우입니다.
- a==c 라면 a도로(이자 c도로)의 방향은 무조건 정해집니다. 다른 경로가 없기 때문입니다. b<d 일때 a or a절을, b>d 일때 ~a or ~a 절을 추가해주면 됩니다.
- 마찬가지로 b==d 라면 b도로(이자 d도로)의 방향은 무조건 정해집니다. a<c 일때 b or b 절을, a>c 일때 ~b or ~b 절을 추가해주면 됩니다.
a != c 이고 b != d 라면, 드디어 앞에서 분배법칙을 사용해 정리했던 논리식을 사용할 수 있게 됩니다. a or b, a or c, d or b, d or c 이렇게 4개의 절을 추가해주면 됩니다.
'PS 풀이' 카테고리의 다른 글
| [백준 33562] shapex (0) | 2025.09.28 |
|---|---|
| [백준 27904] 키파-틱택토 (0) | 2025.09.05 |
| [백준 34019] [G] Grounded Number (0) | 2025.08.11 |
| [백준 18789] 814 - 2 (11008점) (0) | 2025.07.03 |
| [백준 7659] Rubik 2^3 (0) | 2025.04.18 |
