2018. 4. 25. 21:53, 알고리즘/BOJ
https://www.acmicpc.net/problem/1179
M은 별로 크지 않은데 N이 굉장히 커서 뭔가 다른 접근법이 필요합니다. 마찬가지로 귀납적 관점에서 생각하지만, 이전과는 다르게 M, 2M, 3M, 4M, ...을 싹 날린 후의 상태를 생각해봅시다. 예를 들어 (10, 3)의 경우,
1 2 3 4 5 6 7 8 9 10 -> 1 2 X 4 5 X 7 8 X 10의 상태를 생각해보면 이 상황에서 문제를 해결하는 것은 곧
2 3 X 4 5 X 6 7 X 1으로 관점을 바꾸어보았을 때 (7, 3)의 답을 구해서 그것에 대응되는 원래의 값을 찾아주기만 하면 됨을 알 수 있습니다.
일단 계산하기 편하게 M이 N의 약수여서 X가 깔끔하게 떨어지는 경우를 생각해봅시다.
1 2 3 4 5 6 7 8 9 10 11 12
-----------------------------------
1 2 X 4 5 X 7 8 X 10 11 X 을
1 2 X 3 4 X 5 6 X 7 8 X 으로 바꾸어 생각. (8,4) = 6임은 이미 알고있다고 가정.
그러면 6에 대응되는 8이 정답임을 알 수 있고, 6에 8이 대응됨은 (6-1)*M/(M-1)+1을 통해 알 수 있습니다. 이게 왜 되는지는 직접 1, 2, 3, ... 등에 대해 대응이 어떻게 가는지를 확인하면 확인할 수 있을 것입니다.
이제 (10, 3)과 같이 M이 N의 약수가 아닌 경우에는 N%M만큼만 shift 시킨다고 생각하면 됩니다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 9660번: 돌 게임 6 (0) | 2018.04.26 |
---|---|
[BOJ] 1562번: 계단 수 (0) | 2018.04.26 |
[BOJ] 1305번: 광고 (0) | 2018.04.26 |
[BOJ] 11025번: 조세퍼스 문제 3 (2) | 2018.04.25 |
[BOJ] 1168번: 조세퍼스 문제 2 (2) | 2018.04.25 |
[BOJ] 1040번: 정수 (2) | 2018.04.25 |
Comments