책 정리/Programming Challenges : 알고리즘 트래이닝 북
문제 43, 셈, Counting, PC/UVa ID : 110603/10198, 인기도 : B, 성공률 : 높음, 레벨 : 2
최익필
2011. 8. 22. 01:50
문제 43, 셈, Counting, PC/UVa ID : 110603/10198, 인기도 : B, 성공률 : 높음, 레벨 : 2
이 포스트를 만든 목적
- 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.
참조 문헌
- 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 43, 셈, Counting, p.173)
참조 링크
- http://uva.onlinejudge.org/external/101/10198.html : 문제 원문
문제
구스타보는 세는 방법은 배웠지만 숫자들을 쓰는 방법은 이제 막 배웠다. 그는 매우 좋은 학생이며, 이미 1, 2, 3 그리고 4를 배웠다. 하지만 그는 4는 1과 다르다는 것을 아직 깨우치지 못했다. 그래서 그는 4는 1의 다른 쓰는 방법으로 생각한다. 게다가 그는 그가 만든 작은 게임으로 놀고 있다. 이 게임은 숫자들을 합하는 것이다
예
- 132 = 1 + 3 + 2 = 6
- 112314 = 1 + 1 + 2 + 3 + 1 + 1 = 9 (기억해라. 구스타보는 4 == 1 로 생각한다.)
이러한 방법으로 많은 숫자들을 받고, 구스타보는 그 수들의 합이 n을 만드는 수가 몇개인지 알고 싶어한다. 예를 들어 n이 2일 경우, 11, 14, 41, 44 그리고 2로 5개 방법으로 만들 수 있다. 하지만 그는 2보다 큰 n을 알아낼수 없다. 그래서 너에게 도움을 요청한다.
생각/해설
- C1 = {1, 4} = 2
- C2 = {1, 4} * {1, 4} + {2} = 5
- C3 = C2 * C1 + C1 * {2} + {3} = 13
- C4 = C3 * C1 + C2 + C1
- Cn = C(n-1) * C1 + C(n-2) + C(n-3)
- 나는 점화식을 깨우치지 못했고, C4 = C3 * C1 + (?) 이 부분 공식을 못만들어서 시간아 세월아 보냈다.
- 식이 점화식으로 만들어 진다는것을 깨우치면, 코드는 간단하다. 만약 깨우치지 못하면, 백트래킹으로도 풀수 있겠으나, 시간이 너무 오래 걸린다.
입력
- 하나의 수를 입력받는다.
- 각 수는 1 ? n ? 1000 이다
출력
- 주어진 n과 같은 수를 만들 수 있는 가지수를 한 라인에 출력해라.
CODE : solution
CODE : testing
:wq