C/C++로 알아보는

https://www.acmicpc.net/problem/1854

n=1일때는 자명하게 다익스트라로 구할 수 있다. 다익스트라로 1번째 최단경로를 구하는 과정을 다시 곱씹어보자.

이때까지의 모든 방문에 대해 방문하지 않은 모든 정점을 방문하고, 1번째 최단경로를 갱신한다. 이를 적절히 변형해서 k번째까지 구하면 된다.

우선순위 큐에는 아직 갱신되지 않은 적절한 경로들이 들어있다고 하자. 우선순위 큐의 정렬 순서는 경로의 길이이다. 우선순위 큐에서 경로 하나를 pop하자. 이 경로의 최종 정점에 인접한 모든 정점들로 가는 전체 경로들을 우선순위 큐에 넣자. 이렇게 되면 각 최종 정점으로 가는 새로운 경로가 생긴다. 이때 최종 정점 중 한 번 이상 방문한 경우 우선순위 큐에 넣는 과정을 생략하면 1번째 최단경로를 다익스트라를 이용해 구할 수 있다.

일정 횟수 이상 방문을 제한하는 것으로 k번째 최단경로도 쉽게 구할 수 있다. 위 과정에서 방문 횟수가 k 미만인 경우 우선순위 큐에 넣고, k 이상인 경우 넣지 않는 것으로 충분하다.

먼저, 1번 정점으로 가는 길이 0의 경로를 우선순위 큐에 넣고 시작하자. 반복문을 통해 우선순위 큐에서 경로 하나를 pop한다. 그리고 이 정점의 방문횟수를 추가한다. 이 방문횟수는 이 경로가 몇 번째 최단경로인지를 의미한다. 이 정점과 연결된 모든 k번 미만 방문한 정점에 대해 이 경로 뒤에 그 정점을 추가해 우선순위 큐에 집어넣는다. 

이 로직의 정당성은 아래 과정을 통해 보일 수 있다.

1. 경로를 우선순위 큐에 넣고 순서대로 탐색했기 때문에, 정점을 방문할 때 사용한 경로 가운데 k번째 경로를 반환한다.

2. 누락되는 경로는 없다. 만약 존재한다면, 다시말해 적절한 시점에서 우선순위 큐의 경로 길이 length에 대해 우선순위 큐에 한 번도 들어가지 않은 경로 중 length보다 작은 길이의 경로 P가 존재한다면, P의 마지막 정점을 제거한 P-가 우선순위 큐에 들어간 적이 없다는 것이고, P--도 우선순위 큐에 들어간 적이 없다는 것이고, ... 의 과정을 통해 모순을 반환할 수 있다. (1번 정점으로 가는 길이 0의 경로를 넣은 적 없다는 결론을 얻을 수 있으므로)

3. k번을 초과하여 정점 A를 방문한 뒤 B를 방문하는 경로는 B를 k번 이하 방문하는 경로일 수 없다. A를 방문한 뒤 B를 방문하는 k개의 경로가 더 짧은 경로가 되기 때문이다.

마지막으로 경로의 모든 과정을 우선순위 큐에 넣을 필요는 없다. 따라서 경로의 길이와 최종 방문한 정점만 우선순위 큐에 넣는 것으로 해결가능하다.

https://www.acmicpc.net/problem/7420

풀이

자명하게, 맹독 방벽은 건물들의 Convex Hull보다 L이상 떨어져 있어야 한다.

Convex Hull에서 L만큼 떨어진 점들을 모두 모은 폐곡선의 길이를 생각해보자.

Convex Hull에서 L 만큼 떨어진 점들은 Convex Hull을 이루는 선분을 바깥으로 L만큼 평행이동한 부분(위 그림의 검은 선분)을 포함하고, 나머지 부분은 꼭짓점에서 L만큼 떨어진 호(위 그림의 붉은 곡선)가 된다. 이때 검은 선분의 길이 총합은 Convex Hull의 둘레와 같고, 붉은 곡선은 모든 방향의 partition이므로(검은 선분의 양 끝과 Convex Hull의 꼭짓점을 이으면 직사각형이 되고, 평행사변형이므로 붉은 두 선분은 서로 평행하기 때문) 반지름 L인 원의 원주가 된다.

Convex Hull을 찾아 둘레를 구하고, L에 3.1415926*2를 곱한 값을 더해 답을 얻을 수 있다.

https://www.acmicpc.net/problem/1006

문제

초라기는 한국의 비밀국방기지(원타곤)를 습격하라는 임무를 받은 특급요원이다. 원타곤의 건물은 도넛 형태이며, 초라기는 효율적인 타격 포인트를 정하기 위해 구역을 아래와 같이 두 개의 원 모양으로 나누었다. (그림의 숫자는 각 구역의 번호이다.)

초라기는 각각 W명으로 구성된 특수소대를 다수 출동시켜 모든 구역에 침투시킬 예정이며, 각 구역 별로 적이 몇 명씩 배치되어 있는지는 초라기가 모두 알고 있다. 특수소대를 아래 조건에 따라 침투 시킬 수 있다.

1. 한 특수소대는 침투한 구역 외에, 인접한 한 구역 더 침투할 수 있다. (같은 경계를 공유하고 있으면 인접 하다고 한다. 위 그림에서 1구역은 2, 8, 9 구역과 서로 인접한 상태다.) 즉, 한 특수소대는 한 개 혹은 두 개의 구역을 커버할 수 있다.
2. 특수소대끼리는 아군인지 적인지 구분을 못 하기 때문에, 각 구역은 하나의 소대로만 커버해야 한다.
3. 한 특수소대가 커버하는 구역의 적들의 합은 특수소대원 수 W 보다 작거나 같아야 한다.

이때 초라기는 원타곤의 모든 구역을 커버하기 위해 침투 시켜야 할 특수 소대의 최소 개수를 알고 싶어 한다.

풀이

2*n타일링처럼 풀면 된다. 단, 1칸짜리 블럭을 사용한다는 점과 원형이라는 점을 생각해 줘야 한다. 

길이가 2인 방향을 세로, n인 방향을 가로라고 하자.

블럭을 어떻게 쌓을 수 있을까를 생각해 보자. 가로방향으로 이동하면서 DP배열을 채워나간다.

바깥에 있는 구역은 어떤 구역과도 연결되어있지 않거나 안쪽 구역과 연결되어있거나 왼쪽 구역과 연결되어있거나 오른쪽 구역과 연결되어있을 수 있다. 반대로, 어떤 구역과도 연결되어있지 않거나 안쪽에 있는 구역은 바깥쪽 구역과 연결되어있거나 왼쪽 구역과 연결되어있거나 오른쪽 구역과 연결되어있을 수 있다. 안쪽 구역이 바깥쪽 구역과 연결되어있다면 같은 세로줄의 바깥쪽 구역은 안쪽 구역과 연결되어있어야 하므로 한 개의 세로줄이 가질 수 있는 연결의 방법은 총 10가지이다.

10가지 경우에 대해 다음 DP배열을 채울 때 가능한 연결 방법이 있고 불가능한 방법이 있다. 따라서 가능한 모든 방법을 토대로 DP 배열을 채우면 된다.

마지막으로 모든 배열을 다 채웠다면 첫 번째 세로줄과 마지막 세로줄을 비교하면서 가능한 모든 연결방식의 DP 배열의 값을 더해주면 된다. 

실제로 10가지 모든 경우의 수를 하드코딩해서 해결했다. 

먼저 각 세로줄이 왼쪽과 연결되어있는지, 오른쪽과 연결되어있는지를 크기 10인 배열로 미리 저장해둔다. 바깥쪽이 왼쪽과 연결되어있다면 2, 안쪽이 왼쪽과 연결되어있다면 1, 둘 다 연결되어있다면 3, 둘 다 연결되어있지 않다면 0으로 두고 해결했다. 오른쪽도 마찬가지로 미리 저장해서 해결했다. 

k번째 경우의 수의 왼쪽 모양을 left[k], 오른쪽 모양을 right[k]라고 두면 아래와 같이 미리 모양을 만들어둘 수 있다.

왼쪽의 경우와 오른쪽의 경우를 분리한 이유는 i번째 세로줄과 i+1번째 세로줄이 연결될 수 있는지 확인하기 위해 right[i]==left[i+1]을 바로 이용하기 위해서이다. 0번과 1번의 경우 left와 right가 동일한데, 이를 구분해 줄 방법이 필요하다.

어떤 칸이 왼쪽 또는 오른쪽과 연결되어있는 경우 이를 0.5개의 소대를 사용한다고 생각해도 동일한 답을 얻을 수 있다.

이때 각 세로줄이 연결상태에 따라 사용할 소대의 수를 미리 계산해서 넣어두자. 

소수를 저장하게 되는 것은 마음에 들지 않는다. 두 배 해서 저장해 두고 마지막 최종 답을 구할 때 2로 나누자. 두 배 한 뒤의 최종 답이 홀수가 나오는 경우는 없다.

다음으로 DP배열을 구성하자. 

DP[x][type]=> 마지막이 type으로 끝나면서 x번째 세로줄까지의 최적해라 두면, 

DP[x][type]는 left[type]와 right[pretype]의 값을 같게 만들면서 연결되어  있는 소대의 총원이 W보다 작게 되는 모든 pretype에 대해 DP[x-1][pretype]의 합과 같다.

이런식으로 DP배열을 모두 채운다. 

단, 마지막 세로줄의 경우 DP배열을 채울 때 한가지 더 고려해 줘야할 대상이 있다. 바로 첫 번째 세로줄과 연결할 수 있는지 여부이다. right[x]에 따라 첫 번째 세로줄과 연결했을 때 소대의 총원이 W보다 큰 경우가 있다면 최적해 계산에서 제외해 줘야 한다. 

마지막으로, 이렇게 채워진 DP[N-1] 배열의 최소값을 찾아 "2로 나눈" 값이 정답이 된다.

https://www.acmicpc.net/problem/9661

문제.

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 4^x개 만큼 가져갈 수 있다. 즉, 가능한 개수는 1, 4, 16, 64, ...개 이다. 4^x개만큼 돌을 가져갈 수 있는 방법이 없는 사람이 게임을 지게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력.

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000)

풀이.

상대 플레이어가 돌을 몇 개 가져가던 관계 없이 두 플레이어가 가져가는 돌의 합이 5의 배수가 되도록 할 수 있다.

4^n은 5로 나눈 나머지가 1 또는 -1이기 때문에 상대가 나머지 1인 돌 개수를 가져갔다면 4개를, 상대가 나머지 -1인 돌 개수를 가져갔다면 1개를 가져가는 것으로 해결가능하다.

따라서 탁자 위에 돌의 개수가 4개 이하인 경우만 살펴 주면 되고, 돌의 개수가 0개 또는 2개인 경우가 지는 경우이다. 따라서 n을 5로 나눈 나머지에 따라 답을 출력할 수 있다.

이런 류의 게임에서는 상대가 가져간 돌의 개수와 반대되는 개수를 가져갈 수 있도록 반복 단위를 설정할 수 있다면 쉽게 해결된다.

https://www.acmicpc.net/problem/24678

문제.

3개의 돌무더기에 돌이 각각 x,y,z 개 있다. R과 B가 이 돌무더기에서 게임을 한다. 각 플레이어는 다음의 한 가지 시행만을 할 수 있다.

• 돌이 있는 두 개의 돌무더기를 골라, 돌을 하나씩 가져가고, 나머지 하나의 돌무더기에 돌을 하나 추가한다.

더 이상 시행을 할 수 없는 사람이 이긴다.

R와 B가 최선을 다했을 때 이기는 사람을 출력하여라. 게임은 R이 먼저 시작한다.

입력.

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.

다음 T줄에 각각 세 개의 정수 x, y, z가 주어진다.

제한.

•  1≤T≤200000
•  1≤x,y,z ≤10^9

풀이.

x,y,z 범위로 생각했을 때 DP로는 해결 불가능하다.

각 플레이어가 할 수 있는 행동은 다음과 같다.

어...? 각 행동을 할 때 마다 전체 돌의 개수는 1개 줄어든다.

a = x+y, b = y+z, c = z+x로 두자. 그러면 행동에 따른 돌의 개수 변화는 다음과 같다.

문제를 변형해보면, 돌무더기 a, b, c에서 한 번에 두개씩만 가져갈 수 있는 게임이 된다.

각 돌무더기에서는 최대 a/2, b/2, c/2번 가져갈 수 있다. 또, 더 이상 게임을 진행할 수 없다는 것은 "a, b, c중 어느 하나의 돌의 개수가 0인 것"과 같다.

예를 들어 a가 0이 되었다면 a=x+y이고 x, y는 0보다 큰 정수이므로 x=0,y=0이 되기 때문에 원래 문제에서의 "돌이 있는 두 개의 돌무더기를 골라"를 할 수 없기 때문이다. b 또는 c가 2 이상일지라도 z에서 두 개의 돌을 가져갈 수 없다.

따라서 a/2+b/2+c/2-2번 가져가고 나면 그 다음 플레이어는 게임을 진행할 수 없게 된다. 처음 가져가는 플레이어가 R이므로 a/2+b/2+c/2-2가 짝수이면 R, 홀수이면 B가 승리한다.

다시 식을 정리하자. a/2+b/2+c/2=(a+b+c)/2-(a,b,c중 홀수의 개수)/2=(x+y+z)-(x, y, z가 모두 홀수 또는 짝수이면 0, 아니면 1)이고, 이 값의 홀짝 여부에만 종속되므로 (x, y, z의 홀수 개수) - (x,y,z가 모두 홀수 또는 짝수이면 0, 아니면 1)와 같다.

x,y,z의 경우의 수에 대해 표로 정리하면

과 같고, 결과가 홀수일 때 B, 짝수일 때 R이 승리하는 것과 같다.

문제를 보자마자 전체 돌의 개수가 1씩 감소하는 것을 확인하고 더하고 빼고 하다보면 한 돌무더기에서만 돌을 가져가는 문제로 변형할 수 있어 보여 시도해서 정답을 얻었습니다.