프로젝트 오일러 76번

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

---

자연수 5를 두 자연수 이상의 합으로 나타내는 서로 다른 방법은 위와 같이 6가지가 있다.

자연수 100을 두 자연수 이상의 합으로 나타내는 서로 다른 방법은 몇 가지가 있을까?

 

이 문제를 풀기 위해서는 31번 문제를 잘 이해하고 와야 한다.

31번 문제를 이해했다면 76번은 31번과 유사한 문제로 변형하여 빠르게 해결할 수 있다.

76번 문제를 31번과 유사한 문제로 변형하면 다음과 같다.

 

동전의 종류가 1원, 2원, ..., 100원 짜리 까지 총 100가지 있을 때, 동전을 2개 이상 사용하여 100원을 지불할 수 있는 경우의 수는 몇 가지 인가?

 

이렇다면 31번과 동일한 문제가 된다. 다만 100원짜리 동전 하나만 사용하는 경우는 제외해야 하기 때문에 31번과 똑같은 방법으로 접근하여 답을 얻어낸 후, 1가지만 빼주면 76번의 정답이 된다.