풀이
빙고를 풀면 된다. 뭔...
구분을 위해 아래와 같이 표를 만들었다.
우선 조건없이 색칠 가능한 칸을 찾아보자.
이제부턴 추리를 해야한다.
C1이 참이라 가정을 해보자.
A1, B2, C3, D4, E5가 참이여야 한다.
B2에 의해 최소 한개의 세로 빙고줄이 있어야 하지만,
B1에 의해 E1은 색칠될 수 없고, D3의 조건에 부합하지 못해 결국 아무런 세로 빙고줄이 만들어지지 않는다.
C1이 아니므로 불가능 표시(검정색)를 해주었고, 다음으로 A1이 성립하지 않는경우로 추리해보겠다.
E2는 진행에 따라 다르니 일단 C4가 참이라고 가정하고 계속 진행해보겠다.
E2와 E3만 성립한다면, B2는 참이다.
일단은 아직까지는 전부 성립한다.
남은 칸들에 대해 진행을 해보자.
D3이 성립하는지 살펴보자.
기존희 흰칸에 대해서는 성립한다.
하지만, 이미 색칠된 칸의 조건을 충족시키지 못한다.
따라서, D3은 불가능으로 가정, 추가로 A3또한 성립하지 않는다.
+ D5는 이미 성립했어야 한다. 위에서 빠트린 듯 하지만 D3 가정의 결과에는 영향을 끼치지 않는다.
계속 가정이라 표현하는 이유는 모든 칸에 대해 성립하지 않을경우 결국 B2가 맞다고 가정한 순간이 틀린것이기 때문이다.
다음으로 D1, D4가 성립한지 살펴보자.
C5는 당연히 아니다.
하지만, B3을 증명하기 위해서는 D2로 인해 더이상 증명이 불가능하다.
D1, D4가 성립하지 않다고 가정해보겠다.
4개(B1, B3, C4, C5)로 성립하지 않는다.
불가능으로 가정하고 돌아가겠다.
불가능이다.
따라서 다시 D1, D4가 성립하는 가정으로 돌아오겠다.
이렇게 되면 답이 두개가 나온다.
D1, D4의 유무에 따른 버전이다.
마지막 B5를 보자.
이 문제의 정답은 1개가 아니다. 참이다.
하지만 B5를 색칠하면, D2가 성립하지 않는다.
따라서 답은 한개로 D1, D4가 색칠되지 않은 버전이다.
풀이 과정이다.
소스코드
출처
17106번: 빙고
한 줄에 5개의 글자, 총 5줄을 출력한다. 각 줄은 순서대로 빙고판의 각 행을 나타낸다. 색칠된 칸은 "#", 색칠되지 않은 칸은 "."로 따옴표 없이 나타낸다. 예를 들어 A1, C3, C4만 색칠하려면 다음과
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 21335] Another Eruption [Python] (0) | 2023.06.12 |
|---|---|
| [백준 21736] 헌내기는 친구가 필요해 [Python] (0) | 2023.06.10 |
| [백준 20529] 가장 가까운 세 사람의 심리적 거리 [Java] (0) | 2023.06.07 |
| [백준 14940] 쉬운 최단거리 [Java] (0) | 2023.06.07 |
| [백준 18110] solved.ac [Python] (1) | 2023.06.06 |