[백준] 33852. PNUPC 1K9

newbieski·2025년 5월 19일
0

백준

목록 보기
246/246

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개)
profile
newbieski

0개의 댓글