코드포스 1312C 부연설명: 탐욕적인 알고리즘의 정당성에 대해

시청자분께서 질문한 내용에 대답했던 것을 정리한 것입니다.

문제 링크: https://codeforces.com/contest/1312/problem/C

k^i를 빼야 하는 시점에서 뺄 수 있는 수를 아무 것이나 하나 찾아 빼는 과정을 거쳐서 항상 해답이 있는지(출력해야 할 것이 YES인지) 알 수 있는가?

전제: k>=2(k=1일 때에는 답이 항상 YES이다.)

• 배열 a의 a[j]>k^i인 유일한 원소 a[j]가 있을 때 k^i를 빼지 않고 해답을 찾는 경우가 존재하는가?
  • k>2인 경우 k^i를 건너뛴 뒤 k^i 이후로 빼게 되는 모든 수(k^(i-1)부터 1까지)를 모두 빼도 k^i보다 작다. 따라서 k^i를 뺄 수 있을 때 빼지 않으면 이후로 다 빼도 a[j]를 0으로 만들 수 없다.
• 배열 a에 a[j]>=k^i인 원소가 둘 이상일 때, 어느 쪽에서 빼야 해답을 찾을 수 있는가?
  • 한 쪽에서 k^i를 뺀다면 다른 쪽에서 k^i 이후로 뺄 수 있는 모든 수를 빼도 0으로 만들 수 없다. 한번에 한 곳에서만 뺄 수 있다. 따라서 어느 쪽에서 빼도 결론은 NO가 되므로 어느 쪽에서 빼도 상관없다.