백준 1399 풀이
-
[백준] 1399 - 보물의 위치 힌트, 풀이 및 코드 (C++)2022.08.23
[백준] 1399 - 보물의 위치 힌트, 풀이 및 코드 (C++)
https://www.acmicpc.net/problem/1399
1. 문제
- dig라는 함수를 다음과 같이 정의하자.
$dig(x) = x(0 \leq x \leq 9)$
$\cdot dig(x) = dig(x의 모든 자리수의 합) (x \geq 10)$
- 각 테스트케이스에 $M$, $K$가 주어진다. ($M \leq 1,000 , K \leq 10^9$)
- 초기에 (0, 0)에서 북쪽을 바라보고 있으며 초기값이 1인 골드 넘버 대해, $dig(골드 넘버)$만큼 앞으로 가고 90도 오른쪽으로 회전한 뒤, 골드 넘버에 $M$을 곱하는 것을 $K$회 반복한다.
- 위 작업을 실시했을 때 최종 위치는 어디인가?
2. 힌트
힌트 1
$K$가 $10^9$이라는 무지막지하게 큰 수이므로, 당연히 일일히 다 곱하면서 진행할 수는 없다.
또한, $M$을 $K$번 곱해버리면 당연히 무지막지하게 큰 수가 나오기 때문에, 제곱 등을 활용해서라도 $M$을 $K$번 전부 곱하는 행위는 불가능하다.
$dig(x)$의 최종 값은 반드시 0 이상 9 이하라는 점에 주의하며 반복 횟수를 줄여보자.
힌트 2
$x$를 $a + 10b + 100c + \dots $라고 했을때, $x*M = a*M + b*M + c*M + \dots$임을 활용하자.
힌트 3
$dig(x)$의 값은 0 이상 9 이하이고, $dig(x*M)$의 값도 0 이상 9 이하이다.
또한, $dig(x*M) = dig(dig(x)*M)$임을 생각하면 반복하는 중 반드시 반복되는 경우가 나온다.
이제 이를 활용하여 잘 구현해 보자.
3. 문제 관찰 과정 및 풀이
3-1. 문제 관찰 과정 및 풀이
처음 문제를 보면, $K$의 값이 너무나도 크기 때문에 직접 돌려보는 것은 아예 불가능하다는 것을 파악할 수 있다.
따라서, 반드시 반복 횟수를 줄일 수 있는 수학적 방법이 존재함을 고려할 수 있다.
우선 첫 번째 예제 케이스를 직접 계산해 보면서 규칙을 찾아보자.
$K=5, M=2$인 상황에서 골드 넘버는 $1, 2, 4, 8, 16$이 되고, $dig(x) = 1, 2, 4, 8, 7$이 된다.
뭔가 부족하니까 K를 늘려서 조금 더 관찰해 보자.
골드 넘버가 $1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024$일때, $dig(x) = 1, 2, 4, 8, 7, 5, 1, 2, 4, 8, 7$이 된다.
...왠지 모르게 숫자가 반복된다는 점을 파악할 수 있지만, 이것만으로는 풀이가 불완전하다.
반복이 일어난다면 어째서 반복이 일어나는지를 파악해야 하므로, 우선 $K$를 획기적으로 줄일 수 있는 방법이 있다는 믿음을 가지고 삽질을 시작하자.
우선 $dig$의 정의는 숫자 각 자리의 합으로 이루어져 있다는 것을 확인할 수 있다.
그러면 $dig(x)$와 $dig(x*M)$의 관계성을 분석하기 위해선, $x$와 $x*M$의 각 자리의 합을 생각해야 한다.
$x$의 각 자리수를 분해하여 $x$를 $a + 10b + 100c + \dots $라고 하면, $x*M = a*M + b*M + c*M + \dots$ 라는 사실은 쉽게 확인할 수 있다.
그런데 $dig(x) = a + b + c + \dots$이고, $x*M = a*M + b*M + c*M + \dots$이므로 $dig(dig(x)*M) = dig(x*M)$이라는 사실을 확인할 수 있다!
또한, 위 성질을 연장하여 $dig(dig(dig(x)*M)*M) = dig(dig(x*M)*M)$라는것 또한 알 수 있으므로, 어떤 $x$에 대해서도 $dig(x*M^y)$의 계산에서 $M$을 $K$번 곱하지 않고도 구할 수 있음을 확인할 수 있다.
다음은 $dig(x)$의 값이 반드시 0 이상 9 이하라는 점에서 주목해 보자.
$dig(dig(x)*M) = dig(x*M)$의 성질에서 파악 가능하듯, $dig(x*M)$의 값은 $dig(x)$값만 알아도 구할 수 있는데, $dig(x)$의 값은 0 이상 9 이하이므로 어떤 수 $M$에 대해 $dig(x*M)$의 값은 $dig(x)$의 열가지 경우의 수에 대해서만 결정된다.
(TMI: 물론 $dig(x)$의 정의에 의해 $dig(x)$가 0이 되는 일은 없어서 아홉 가지 경우의 수밖에 없긴 하다)
가령, $M=2$에 대해 그 어떤 $x$에 대해서도 $dig(x)=1$이면 $dig(x*M)=2$, $dig(x)=5$이면 $dig(x*M)=1$과 같이 결정된다는 것이다.
이에 따라 반드시 $dig(x) = dig(x*M^y)$인 지점이 생기게 되므로 반복하는 구간이 생기게 되고, 이 주기는 비둘기집의 원리에 의해 최대 10이 된다.
이제 이 주기에 따라 $K$값을 줄여주는 구현을 하면 되는데, 이 구현을 생각하기가 조금 까다로울 수 있다.
필자의 경우, queue에 값을 계속 넣어주다가 이미 들어온 적 있는 값이 queue에 들어오면 해당 값이 front에 올때까지 pop해준 뒤, $K %= 해당 queue의 길이 * 4$ 연산으로 $K$값을 줄여주었다.
이렇게만 줄이더라도 queue의 길이는 최대 10이라는 사실을 파악했으므로 $K$는 40 이하가 되고, 40번까지는 충분히 브루트 포스로 돌릴 수 있으므로 그대로 구현하면 된다.
4. 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dig(int x) {
if (x<10) return x;
int sum = 0;
while (x>0) {
sum += x%10;
x/=10;
}
return dig(sum);
}
int main() {
int t;
cin >> t;
while (t--) {
queue<int> q;
int k, m;
int y=0, x=0;
int dir = 0;
cin >> k >> m;
vector<int> visited(10, 0);
int num = 1;
while (k>0) {
if (visited[num]) {
while (q.front() != num) {
q.pop();
}
k%=(4*q.size());
if (k==0) break;
}
visited[num] = 1;
q.push(num);
switch(dir) {
case 0:
y+=num;
break;
case 1:
x+=num;
break;
case 2:
y-=num;
break;
case 3:
x-=num;
break;
}
k--;
num = dig(num*m);
dir = (dir+1)%4;
}
cout << x << " " << y << "\n";
}
}
5. 여담
처음에 $K$ 나머지 연산할 때 0이어도 계속 진행되게 코드를 구현해서 WA를 띄웠었다.
대회에서 신나게 풀어놓고 저렇게 실수해서 패널티 쌓이면 상당히 슬프겠는데....
'PS > 백준 풀이' 카테고리의 다른 글
[백준] 6132 - 전화선 힌트, 풀이 및 코드 (C++) (0) | 2022.09.07 |
---|---|
[백준] 10542 - 마피아 게임 힌트, 풀이 및 코드 (C++) (0) | 2022.08.29 |
[백준] 2001 - 보석 줍기 힌트, 풀이 및 코드(C++) (0) | 2022.07.30 |
[백준] 1185 - 유럽여행 힌트, 풀이 및 코드 (C++) (0) | 2022.07.10 |
[백준] 3031 - 리그 힌트, 풀이 및 코드 (C++) (0) | 2022.07.09 |