주간 문제풀이 14 (BOJ 7420 / 10265 / 2094 / 3596)

이런 셋을 풀었다.

 

BOJ 7420 - 맹독 방벽 (P5)

문제: 다각형이 주어졌을 때, 이 다각형에서 거리를 L이상 유지하면서 다각형을 두르는 벽의 최소 길이를 구하는 문제

 

풀이:

먼저, 원래 다각형을 해당 다각형의 컨벡스 헐로 바꾼다. (그렇게 해도 답이 늘어나지 않음을 관찰)

 

컨벡스 헐의 간선 하나마다, 해당 간선에서 L만큼의 거리를 두고 같은 길이의 벽을 새로 짓는다고 생각하자. 이제 새로 지은 벽을 이어주어야 하는데, 그렇게 지어야 하는 벽을 모두 합치면 반지름 L의 원이 된다. 따라서 답은 컨벡스 헐의 모든 간선 거리의 합 + 2* PI * L 이 된다.

안쪽 삼각형이 컨벡스 헐이면, 바깥쪽에 벽 3개는 컨백스 헐의 간선에 대응하고, 파란색 간선은 합치면 반지름 L의 원

 

코드: http://boj.kr/44f5fc68b69f45e28f33edc58256dab3

 

 

BOJ 10265 - MT (P4)

문제: N명의 사람이 있고, 버스에는 K명만 태울 수 있다. x_i번째 사람이 버스에 타지 않으면, i번째 사람도 타지 않는다. 모든 사람의 의견을 해치지 않고 최대한 태울 수 있는 인원수를 구하자.

 

풀이:

- 모든 i에 대해 x_i -> i방향으로 간선을 만들어서 그래프를 그리자. 그러면 이 그래프에서 한 노드를 포함하지 않으면 그 노드에서 도달할 수 있는 다른 모든 노드를 포함할 수 없는 것이다. 

- 이 그래프에 대해 scc를 구성해서 scc들 사이의 dag를 그리면, in-degree가 없는 scc에 있는 인원만 항상 가져갈 수 있고, 그 외의 scc에 있는 인원은 의존하고 있는 scc에 있는 인원이 가야 갈 수 있는 걸 확인할 수 있다.

- 잘 생각해보면, indegree가 없는 scc를 제외하고는, 다른 scc의 크기는 모두 1이다. (왜냐하면, 그래프를 만들 때 각 노드의 out-degree가 0 또는 1이었으니까..) 그래서 indegree가 없는 scc를 가져가면, 거기서 연결된 다른 노드들은 정확히 원하는 개수만큼 가져갈 수 있다. 예제 기준으로는 , 4,5,6,7번 사람을 가져가면, 1~10번 노드 중에 원하는 개수만큼 가져갈 수 있다.

- 이걸 연결된 scc들마다 [가져가야 하는 최소 개수, 최소 개수를 가져가고 나면 가져갈 수 있는 최대 개수] 이렇게 정수 쌍으로 표현할 수 있다. (예제는 ([1, 2], [4, 10])) 여기서부터는 0-1 knapsack을 하면 되는데, 각 연결된 SCC마다 (가져갈 수 있는 최소 개수가 A고, 최대 개수가 B면은) A, A+1, A+2, ..., B명을 가져가는 경우를 모두 고려해주면 된다.

코드: https://www.acmicpc.net/source/share/8338f705ea7340c9be2c67fb2c33d50c

공유 소스 보기

 

 

BOJ 2094 - 강수량 (P3)

문제: 각 연도별로 측정된 강수량이 N개 주어진다. 동시에 "X년도에는 Y년도 이후 가장 많은 비가 내렸다" 형식의 주장이 M개 주어지는데, 강수량 데이터를 통해서 이 주장이 참인지, 거짓인지, 또는 알려져 있지 않은 강수량에 대한 가정 하에 가능한지 판단하는 문제다.

 

풀이:

- Y년도와 X년도 사이에 관측되었던 최대 강수량이 얼마인지는, 좌표압축과 세그먼트 트리를 통해 로그 시간에 구할 수 있다.

- Y년도와 X년도 사이에 모든 연도에 대한 강수량 데이터가 있는지는, 이분탐색을 통해서 로그 시간에 구할 수 있다.

이 두 가지 데이터를 가지고 있다면, 나머지는 Y년, X년의 강수량 데이터와 결합해서 케이스를 나눠서 풀면 된다. 조금 더 케이스를 풀어 보자면..

- Y년, X년의 강수량 데이터가 모두 없는 경우: 항상 maybe

- Y년, X년의 강수량 데이터 중 하나만 있는 경우: Y~X년 사이의 최대 강수량과 모순되지 않으면 maybe

- Y년, X년의 강수량 데이터 모두 있는 경우: Y년, X년, Y~X년 사이의 최대 강수량 이 세 값 중 모순이 있으면 false / 모순이 없는데 Y~X년 관측값 중 빠진게 있다면 maybe / 없으면 true

 

코드: http://boj.kr/0eab40412425415b8b17bce3f8a891c4

공유 소스 보기

 

 

BOJ 3596 - 크로스와 크로스 (P2)

문제: 1 * n칸으로 이루어진 보드에서, 두 플레이어가 서로 번갈아가면서 빈 칸 중 한 곳에 x 마크를 한다. 연속된 3개의 x를 만드는 플레이어가 승리한다. n이 주어졌을 때, 이기는 사람을 구하는 문제이다.

 

풀이:

누군가가 x를 이미 놓은 곳과 두 칸 이내로 떨어진 곳에 x를 또 놓게 된다면, 그 즉시 상대방이 승리함을 관찰하자. 즉, 이미 x가 있는 곳과 두 칸 이내로 떨어진 곳은 없는 칸이라고 생각하고 게임을 해야 한다. 그러면 아무 것도 없는 게임판에서 x를 하나 놓았을 때, 게임이 x를 놓은 곳 기준으로 왼쪽과 오른쪽에 있는, 최대 2개의 더 작은 독립적인 게임판으로 분리된다고 생각할 수 있다.

 

그러면 이제 각 게임판 크기마다 그런디 숫자를 부여해서, 스프라그 그런디 정리로 문제를 풀 수 있다. 구체적으로는 x를 놓을 수 있는 각 위치마다, 해당 위치에 x를 놓았을 때의 그런디 숫자를 구해서, 모든 후속 상태의 그런디 숫자의 mex를 구하면 된다.

코드: https://www.acmicpc.net/source/share/0efe79f9743f480494816a68996e6420

공유 소스 보기