문제 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


'책 정리 > Programming Challenges : 알고리즘 트래이닝 북' 카테고리의 다른 글

문제 44, 표현식, Expressions, PC/UVa ID : 110604/10157, 인기도 : C, 성공률 : 보통, 레벨 : 2  (1) 2015.02.04
문제 42, 땅 나누기, How many Pieces of Land?, PC/UVa ID : 110602/10213, 인기도 : B, 성공률 : 보통, 레벨 : 2  (1) 2011.08.01
문제 41, 피보나치 수의 개수, How many Fibs?, PC/UVa ID : 110601/10183, 인기도 : B, 성공률 : 보통, 레벨 : 1  (0) 2011.07.29
문제 40, 모든 쌍의 합, Pairsumonious Numbers, PC/UVa ID : 110508/10202, 인기도 : B, 성공률 : 높음, 레벨 : 4  (0) 2011.07.27
문제 39, 스턴-브로콧 수체계, The Stern-Brocot Number System, PC/UVa ID : 110507/10077, 인기도 : C, 성공률 : 높음, 레벨 : 1  (0) 2011.07.03
문제 38, 다항식의 계수, Polynomial Coefficients, PC/UVa ID : 110506/10105, 인기도 : B, 성공률 : 높음, 레벨 : 1  (0) 2011.06.14
문제 37, 곱하기 게임, A Multiplication Game, PC/UVa ID : 110505/847, 인기도 : A, 성공률 : 높음, 레벨 : 3  (0) 2011.05.07
문제 36, 1의 개수, Ones, PC/UVa ID : 110504/10127, 인기도 : A, 성공률 : 높음, 레벨 : 2  (0) 2011.05.05
문제 35, 고고학자의 딜레마, The Archeologist's Dilemma, PC/UVa ID : 110503/701, 인기도 : A, 성공률 : 낮음, 레벨 : 1  (0) 2011.05.05
문제 34, 뒤집어서 더하기, Reverse and Add, PC/UVa ID : 110502/10018, 인기도 : A, 성공률 : 낮음, 레벨 : 1  (0) 2011.03.10
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 라이프코리아트위터 공유하기
  • shared
  • 카카오스토리 공유하기