https://www.acmicpc.net/problem/33852
문제요약
- 36진수가 주어짐(길이 100000)
- k, p가 주어짐(k<p<1000)
- 36진수 숫자를 적절히 바꿔서 mod p에서 k가 되도록 최소 변경 회수 구하기
접근법
- 여러가지 풀이가 있겠으나
- 각각의 자리수를 바꾸었을때 나오는 결과의 경우의 수는 최대 1000개임
- 각각의 자리수를 바꿀수 있는 경우의 수는 36
- 즉 36번씩 바꾸어가면서 이전 결과를 이용하여 다음 단계에서 1000개의 경우의수가 어떻게 나오는지를 길이만큼(10만) 반복하는 DP면 좋겠는데
- 문제는 시간복잡도가 너무 큼
- 그런데 관찰을 해보면 최초의 수 a -> 목표의 수 k까지 변환을 시킨다고 할때
- 36진수 숫자하나를 바꾸면 a가 아닌 다른 수가 될 것임.근데 이러한 수는 최대 1000개만 유효함
- 1 -> 3 -> 4 -> 5 -> 3 -> 7 로 숫자를 바꿀때마다 변한다고 할때
- 두번째 나오는 3은 의미가 없음. 이미 앞에서 3이 가능하기때무에
- 즉 최대 유효한 변환의 수는 1000개(=p개)
newbieski