2016 KOI 지역본선 49번

오늘 마킹 실수든, 옮겨 적는데 실수를 했건, 어쨌든 어느 부분에서 실수가 일어났음을 새로 알게된 문제이다.

 

대회 당시 풀 때에 문제를 읽고, 방법을 떠올려 바로 4라는 답을 낸 것 같은데, 옮긴 답에는 이상한 수가 적혀있다(정작 48번에 4가 적혀있더라...어찌된 일인지는 결과가 설명해줄 듯하다). 아무래도 이번 지역본선은 나와 전혀 맞지 않았던 것 같다.

 

여튼, 문제를 설명하자면

'임의의 자연수 n에 대해  1이 될 때까지 우박수 시행을 한다. 이 때, 7번의 시행으로 1이 되는 자연수 n의 갯수를 구하시오.'

이다.

 

이 문제는 1이 되기 위해서는 2^k 꼴로 변형되어야지만 가능함을 이용하여 해결할 수 있다.

 

7회의 우박수 연산으로 1이 되는 최대 2^k은 2^7인 128이하여야 한다. (3n+1을 시행하는 경우는 시행한 이후의 수가 현재의 수보다 더 커지므로 2로 나누는 경우를 7번 시행하여 1이 되는 수들은 128보다는 작거나 같아야한다.)

 

쉽게 접근하기 위해서 7번의 시행으로 1이 되는 수는 중간 과정에 2^k 꼴로 나타나는 수가 존재함을 이용한다. 이를 역으로 생각하면 2^k 꼴로 나타나는 수로부터 (7-k) 의 연산으로 만들 수 있는 수를 나열하는 방법을 생각해보자.

 

1) 7 이하의 음이 아닌 정수 k에 대해 2^k을 모두 나열한다.

2) 이후, 각각의 2^k 에 해당하는 수들이 어떠한 n에 대해 2^k = 3n +1 로 나타난다면, 해당하는 n도 나열한 수들에 추가한다.

3) 새로 추가된 수들 중 하나를 n이라고 하면, 2*n인 새로운 수를 추가시킨다. 만약 임의의 p에 대해 n = 3p + 1 의 꼴로 나타날 수 있다면 p도 나열한 수들에 추가한다.

4) 새로 추가되는 수가 없을 때까지 반복한다. (단, 시행 횟수가 7 이상인 수들에 대해서는 2~4 수행을 하지 않는다.)

임의의 수에 대해 우박수 시행을 하여 1이 되는 경로는 유일하기 때문에 수의 겹침을 고려하지 않아도 된다.

 

위와 같은 방법을 통해 만들어진 수들 중, 시행 횟수가 7인 수들이 7번의 우박수 시행으로 1이 될 수 있는 수들이다. 

이유는 위 방법을 통해 얻어낸 수들은 시행 횟수가 7 이하인 수들임이 보장되기 때문이다(시행이 0인 수가 유일하고, 이 수부터 1씩 시행을 증가시킨 수들을 만들어가므로). 128보다 작아도 시행이 7번이 넘어가는 수들은 만들어지지 않으므로 꽤 좋은 효율을 보일 것처럼 보인다.

 

아래는 7번의 시행에 대해 1~4 단계를 거친 결과이다.

 

 

제시한 방법을 실제로 해보면 생각보다 매우 깔끔하게 나온다. 수를 나열할 때 시행 횟수 칸에 맞추어 적으면 더 보기 편할 것이다.