백준 21794 Navigation 2 (JOISC 2020/2021 Day 4 2번)

문제 설명(링크)

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

21794번: Navigation 2

 

풀이

14는 조금 어렵고, 13은 어렵고, 12는 더 어렵다.

 

14 풀이

x좌표, y좌표가 3의 배수인 칸마다 14를 쓴다. 하나의 14 주위의 8개의 칸을 다음과 같이 번호를 붙이자.

0 1 2

3 14 4

5 6 7

 

7번 칸은 현재는 사용하지 않는다. 아무 수나 채우자.

 

14가 가운데에 위치한 3*3의 영역을 블럭이라 하자. 한 블럭의 14를 기준으로, 그 블럭과 $i$번째 도착점의 상대적인 위치관계를 아래 표와 같이 표시하자. 14가 있는 칸에 도착점이 있으면 5, 한칸 위에 있으면 2, 한칸 오른쪽에 있으면 6이 되는 방식이다.

12	12	12	12	12	12	12
12	12	12	12	12	12	12
12	12	1	2	3	12	12
10	10	4	5(14가 있는 칸)	6	11	11
13	13	7	8	9	13	13
13	13	13	13	13	13	13
13	13	13	13	13	13	13

한 블럭의 0-6의 위치에 대해 각 칸을 기준으로 하는 상대적인 위치를 작성한다. 이렇게 하면 14 주위 8칸에서 각 도착점으로 가기 위해 어디로 가야 하는지 찾을 수 있다. 

 

12	2	7
1	3	14
2	5	12

위와 같이 쿼리가 주어진 경우를 보자. 우선 가운데 칸을 $(a, b)$라 하자. 14가 한칸 오른쪽에 있으므로, $(a, b-2)$에도 14가 쓰여 있다. 따라서, 14가 아닌 수들은 다음과 같은 번호의 도착점을 나타내고 있다.

2	0	1
4	3	x
x	5	6

 

0번 도착지점의 경우, $(a-1, b)$을 기준으로 바로 한 칸 위에 위치한다. 즉 좌표는 $a-2, b$이고, 위로 이동해야 한다.

6번 도착지점의 경우, 목적지로 도달하기 위해서는 위쪽과 오른쪽으로 적어도 두 번 이동해야 한다. 따라서 도착지의 $x$좌표는 $a-1$ 이하이다. 따라서 위쪽으로 가도 된다.

이와 같은 방법으로 모든 지점에 대해 답을 구할 수 있다.

 

13 풀이

이젠 13을 쓴 칸이 14 풀이의 14를 쓴 칸 역할을 대신한다. 13을 쓴 칸이 꼭 x, y 좌표가 3의 배수일 필요는 없다. 제일 왼쪽 위의 14 칸으로 가능한 9가지 선택지가 있는데, 이 중 2개의 경우는 반드시 다음 조건을 만족한다.

 

* 14의 풀이대로 숫자를 적었을 때, 14가 적히지 않은 모든 칸 $(a, b)$에 대하여 숫자 5가 한 번도 사용되지 않는 경우가 있다.

 

비둘기집의 원리로 증명할 수 있다. 제일 왼쪽 위의 14 칸으로 가능한 9가지 선택지가 있는데, 도착지는 7개이기 때문이다.

따라서 도착지의 상대적인 위치를 표시할 때 숫자 5는 사용하지 않으며, 따라서 12개의 숫자만으로도 할 수 있다.

 

11	11	11	11	11	11	11
11	11	11	11	11	11	11
11	11	1	2	3	11	11
9	9	4	필요 없다	5	10	10
12	12	6	7	8	12	12
12	12	12	12	12	12	12
12	12	12	12	12	12	12

 

12 풀이

12의 풀이와 유사하다. 도착지의 상대적인 위치를 표시할 때 기준이 되는 칸 주위의 칸들을 표시하기 위해 8개의 숫자를 쓰고, 멀리 있는 칸들을 표시하기 위해 4개의 숫자를 쓴다. 이때, 처음 8개의 숫자가 모두 쓰이지 않는다. 왜냐하면, 각 도착지 $i$를 표시하는 칸들은 $x$, $y$좌표 모두 거리가 3씩 띄워져 있어서 이들 중 1-8의 숫자를 사용하는 칸은 최대 하나밖에 없기 때문이다. 이로 인해 1-8의 숫자 중 최대 7가지의 숫자만 쓰여서 비둘기집의 원리에 의해 성립한다.

 

앞에서는 사용하지 않았던 7번 칸에 이 사용되지 않은 수를 적어두자. 이 수를 $x$라 하면, $x$초과의 모든 수는 1을 빼서 쓰고, 그렇지 않은 수는 그대로 쓰자. 이렇게 하면 B 입장에서는 12의 위치를 통해 $x$를 복원하여 원래 배열을 복원할 수 있다.

 

소스코드

https://oj.uz/submission/478043

답안 #478043 :: oj.uz