BOJ - 우표 구매하기 (Hard)

• https://www.acmicpc.net/problem/13542

Idea

• 생성 함수를 정리하면 식이 하나 나온다.
• 그 식은 무한합 x 무한합 꼴이라 계산하기 어렵다.
• 합차공식을 이용하여 분모엔 무한합을(중복 조합), 분자엔 유한합을(이항 계수) 남겨둔다.
• 그럼 $x^K$의 계수를 $O(N)$에 계산할 수 있다.

Reflection

• 생성 함수는 잘 나왔는데, 거기서 어떻게 $K$번째 항을 뽑아낼 지 모르겠어서 답을 봤다.

Takeaway

• 이런 문제를 풀 때 가져야 할 태도

  • 일단 생성 함수를 만들자.
  • 계산 가능한 꼴 및 잘 알려진 생성함수로 변환이 가능하도록 최대한 노력한다. (유한합이 포함된 식)
  • 분모에는 $(1-x^{k})^{n}$ 꼴을 만들어 중복 조합 및 이항 계수로 풀어쓰고(무한합), 분자에는 $(1 \pm x^ k)^{n}$ 꼴을 만들어 이항 계수로 풀어 쓰는 게 좋다. (유한합)

• 느낀 점, 교훈

  • 생성 함수를 실제로 PS에서 어떻게 쓰는지를 알게 해준 문제였다.
  • 식 정리를 다방면으로 해보자.

Useful Links

• https://infossm.github.io/blog/2019/10/19/generating-function/