아희PS - BOJ 22904 오렌지 수(Platinum III)

이번에 알아볼 문제는 '오렌지 수'라는 문제이다. 문제 링크: https://www.acmicpc.net/problem/22904

22904번: 오렌지 수

지금까지 내가 푼 문제 중에서 가장 티어가 높은 문제라는 점에서 상당히 의미가 큰 문제다. 하지만 생각하는 것 보다 이 문제와 엮인 사연은 중대한데, 그 이유는 여러 가지가 있다.

첫째, 문제의 출제자가 내가 아는 사람이라는 것

문제의 출제자는 아래의 링크에 나오는 사람이다. 서로 아는 사이인 사람이 낸 문제를 풀어보는 건 꽤나 희귀한 일인 것 같다(나만 아는 사람이야 많지만...)

출제자: https://leinad2.tistory.com/

leinad2가 ps하는 블로그

블로그 글좀 올려 ㅡㅡ

둘째, 내가 문제를 푼 시점은 대회 중이었다는 것

문제 페이지에 들어가 보면 대회의 출처가 'Orange Cup'인데, 출제진 중에 내가 아는 사람이 몇 있었기에 참가해 보았고, 대회 중반 쯤에 이 문제의 풀이를 C++로 짜서 AC를 띄운 후 "아희각"이라는 3글자가 뇌를 지배했다. 그래서 빠르게 아희 코드를 짜서 다시 AC를 띄웠다. A번 문제에서 '예제만' 서브태스크가 있었기 때문에, 이 5점을 포함하여 아희로만 총 105점을 획득했다.

서론은 접어두고, 코드를 보기 이전에 풀이를 알아보자.

풀이

1. 불가능 판별

우선, 모든 자연수 \(n\)에 대하여, \(n\)의 자릿수의 합을 구한다고 하더라도 이 수는 \(n\)과 9로 나눈 나머지가 같다. 결국, \(n\)과 \(n^2\)의 자리수의 합이 같으려면, \(n\)과 \(n^2\)을 9로 나눈 나머지가 같아야 한다. 합동식의 표현을 빌리자면, 답이 존재하는 \(n\)에 대해 다음 식이 성립한다.

$$n\equiv n^2(mod 9)$$

이것을 만족하는 \(n\)은 \(n\equiv 0,1(mod 9)\) 뿐이므로, 9로 나눈 나머지가 2~8인 수들은 답을 찾는 것이 불가능한 수들이다.

2. 답 찾기

그러면 9로 나눈 나머지가 0, 1인 수들에 대해서는 답을 찾을 수 있을까? 나는 예제로 주어진 케이스 중 '99'라는 숫자에 주목했다. 99를 제곱하면 9801이 되므로, 분명히 조건에는 맞는 수이다. 그렇다면, 9를 \(K\)개 쓴 수를 제곱하면? 놀랍게도 9만 여러 개 반복되는 수는 조건을 만족한다.

\(999^2=998001\)

\(9999^2=99980001\)

\(9999^2=9999800001\)

이 수들은 조건을 만족한다. 그런데 3개를 찾으라고 했는데? 그러면 앞을 살짝 바꿔보자.

\(279999^2=78399440001\), 합이 45로 같다.

\(369999^2=136899260001\), 합이 45로 같다.

이렇게 입력값이 9의 배수일때는 저런 방식으로 3개의 답을 출력할 수 있다.

 

이제 9로 나눈 나머지가 1일 때도 같은 짓을 해보자.

\(199999^2=39999600001\), 합이 46으로 같다.

\(559999^2=313598880001\), 합이 46으로 같다.

\(739999^2=547598520001\), 합이 46으로 같다.

이 형태의 수들은 자릿수를 늘려도, 합이 같게 된다.

 

이외의 경우에 대해서는 -1을 출력하기만 하면 된다.

 

3. 아희로 풀기

풀이를 아는게 쉽지는 않을뿐, 코드를 짜기 위해서는 조건/반복문만 쓸 줄 알면 된다. 다음이 코드이다.

방빠밡랴뿌처밡나카카카카빠밡망받반타타뺘쿠처발발다맣밡받따망마받반타타빠밡망받반타타뺘쿠처발발다맣밡밭따망마밡망받반타타뺘쿠처삭해
ㅋㅋㅋㅋ받반타타밡랴뿌처붍코커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코커커커커커커커
ㅋㅋㅋㅋ해석멍터벋번머ㅋ누
뿌뻐커멍벑멍터번벋터터번벋
밡망받반타타뺘쿠처발발다맣발망발망마밡망받반타타뺘쿠처발발다맣밠망받망마밡망받반타타뺘쿠처삭해
코커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코커커커커커커커

코드가 길긴 하지만, 형태는 굉장히 간단하다. 9로 나눈 나머지가 0,1,그 외인 경우를 갈라 주고, 각 경우에 따라 적절히 반복문을 돌려주면 된다. 대회 중이었기 때문에, 원래 스타일도 그렇지만 미학적인 부분을 고려하지 못한 점은 어쩔 수 없었다고 생각한다. 먼저, 처음에 조건 분기를 하는 부분을 살펴보자.

방빠밡랴뿌처밡나카카카카-->(1)
ㅋㅋㅋㅋ받반타타밡랴뿌처-->(2)
ㅋㅋㅋㅋ해석멍터벋번머ㅋ

수를 입력받은 뒤에 복사하고, 9로 나눈 나머지에 따라 분기가 일어난다. 0이라면 (1)로, 1을 뺀 뒤 0이라면 (2)로 진행하며, 아니라면 -1을 출력하고 프로그램을 종료한다. 이제 (1)과 (2)로 나가는 부분에서 어떤 일이 일어나는지를 살펴보자. 아래의 코드는 (1)에 이어지는 코드이다.

밡나카카카카빠밡망받반타타뺘쿠처발발다맣밡받따망마받반타타빠밡망받반타타뺘쿠처발발다맣밡밭따망마밡망받반타타뺘쿠처삭해
ㅋㅋㅋㅋㅋㅋㅋ코커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코커커커커커커커

위에서 (1)로 표시된 부분의 '밡나카카'부터 시작이다. 우선 숫자를 9로 나눈 값을 저장하자.

그리고 코드는 굉장히 단순하게, 3개의 숫자를 출력하는 구조로 되어 있다. 각 부분을 살펴보자.

빠밡망받반타타뺘쿠처
ㅋ코커커커커커커커ㅋ

빠 - 숫자를 복제한다. 이 값을 1씩 줄여나가면서 0이 될 때까지 9를 출력할 것이다.

밡망 - 9를 출력한다.

받반타타 - 복제해둔 값을 1만큼 감소시킨다

뺘쿠처 - 복제해둔 값이 0이 되었다면 오른쪽으로, 아니라면 밑으로 진행한다. 밑으로 진행한 경우 다시 '밡망'부터 진행된다.

이렇게 9를 \(\frac N9\)개 출력했다.

나머지 수를 출력하는 과정도 비슷하다. '발발다맣'을 통해 줄바꿈을 해주고, '27'을 출력하고, \(\frac N9-2\)개의 9를 출력한 뒤, 줄바꿈, 36 출력, \(\frac N9\)개의 9를 출력을 해주면 된다. 특정 개수의 9를 출력하는 방법은 위에서 설명한 바와 같다.

(2) 역시도 위에서 설명한 형태와 같다. 1을 출력하고 \(\frac {N-1}9\)개의 9를 출력, 줄바꿈, 55 출력, \(\frac {N-1}9-1\)개의 9를 출력, 줄바꿈, 73 출력, \(\frac {N-1}9-1\)개의 9를 출력하면 (2)의 경우에도 답을 찾아낼 수 있다. Platinum III이지만, 구현 난이도는 지난 번에 설명한 피보나치 수 코드보다도 간단하다. 아마도 관찰에서 저런 난이도가 매겨진 것 같은데, 지금까지 내가 아희로 푼 문제들 중에는 가장 티어가 높다 보니 소개하게 되었다.