[platinum1] [해설안봄 알고리즘 분류 안봄] boj 2041 숫자채우기

이전에 풀었던 문제로 아이디어성 문제이다. 구현은 쉬우나 규칙을 찾는게 어려운 문제이다.

n*m 크기의 격자에 인접한 수의 차이가 1부터 2nm - n - m 까지 나오게 하는 문제

 

내가 푼 방법대로의 정답을 말하자면

만약 n이 5, m이 5라고 하면 1,1은 1로 시작하고, 1,2은 차이가 40(2nm - n - m ) , 1,3열은 39, 38, 37씩 차이가 나게 한다. 2,1는 1,1 과 36 차이가 나게 한다. 그 후 2,2은 2,1과 36 (2,1 -1,1) - m  = 31 차이나게 한다. 또 2,3 은 2,2와 30 씩, 2,4는 2,3 과 29 씩 차이나게,,,, 이런 규칙을 계속 이어나가면 된다.

5 5

1 41 2 40 3

37 6 36 7 35

10 32 11 31 12

28 15 27 16 26

19 23 20 22 21

 

우선 이 규칙을 증명은 아니지만 이해를 쉽게 하기 위해서 각 행의 규칙에 대해 살펴보자. 각 행의 홀수열은 1씩 증가하게, 짝 수열은 1씩 감소하게 만든다면, 열이 증가할수록 인접한 수의 차이는 1씩 줄어드는 걸 쉽게 알 수 있다.  예를 들면 (5, 39, 6, 38, 7).

 

 

또한 같은 규칙을 따르지만 홀수열은 1 감소, 짝수열은 1증가하는  또다른 행을 생각해보자. ( 25, 11, 24, 12,23) . 이 행의 홀 수열의 차이는 (5, 39, 6, 38, 7) 행의 홀수열의 차이와 20, 18, 16 으로 2씩 감소하는 것을 알 수 있다. 짝수열은 28 , 26 씩 감소 한다.

 

즉 알 수 있는 것은

1. 홀수열과 짝수열끼리 1씩 차이 나게하면 각 열마다 차이는 1씩 줄어들게 된다.

2. 1번의 규칙을 따른 행끼리 열을 빼면 홀수열 ,짝수열 끼리 독립적으로 2씩차이나게 된다.

여기서 중요한 점은 홀수열과 짝수열이 독립적이라는 것이다. 

그럼 홀수열과 짝수열의 숫자의 숫자들을 임의로 조작해서(1번의 규칙은 지키면서)  행끼리의 뺐을 때의 차이를 조절 할 수 있지 않을 까 생각하게 된다. 

이런식으로 가능하다. 그럼 같은행의 열끼리는 1씩 감소하면서, 행끼리의 차이는 조절할 수 있게 된다. 

이걸 5,5 격자에 적용해보면 이렇게 되고, 위에서 생각했던 것처럼 조절을 통해 빨간, 파란 숫자를 독립적으로 조절 할 수 있다.

 

 열끼리의 차이는 유지하면서, 2행의 전체를 3씩 증가하면 다음과 같이 된다.

여기서 유의해야 할 사항은 2행에서 숫자가 증가할 수록, 홀수열과의 차이(빨강)은 3씩 증가하고 짝수열과의 차이는 ( 파랑) 3씩 감소했다는 사실이다. 반대로 2행의 숫자가 감소할 수록, 빨강은 감소하고 짝수는 증가하기 때문에, 적당히 맞춰줘야 원하는 결과를 얻을 수 있다.

 

 한번 이 점에 착안해 이번에는 2행에서의 각열의 차이를 36,35,34,33 로, 각행의 열끼리의 차이를 32, 31,30,29,28 로 만들어 보자. 

 

얼핏보면 이것도 이제 숫자를 잘 조절해서  차이를 32,31,30,29,28 로 만들 수 있을 것 같지만, 위에서 말한 것처럼 행의 숫자를 감소시키면 빨강은 감소, 파랑은 증가하기 때문에 결국 32,31,30,29,28 로는 맞출 수 없다.

 

 

 

따라서 아래와 같은 형태로 1행에서 40,39,38,37, 2행과 1행의 차이에서 36,35,34,33,32 2행에서 31,30,29,28 이런식으로 가능하게 된다/ 

 

 

5 5

1 41 2 40 3

37 6 36 7 35

10 32 11 31 12

28 15 27 16 26

19 23 20 22 21