백준 9095번: 1,2,3 더하기

문제

• https://www.acmicpc.net/problem/9095
• 정수 N을 1, 2, 3의 합으로 나타낼 때 가능한 경우의 개수 구하기

기록 포인트

• 재귀/분할 정복: 분할,정복,결합의 3단계를 문제에 어떻게 적용할 것인가?
  • 현재의 문제를 같은 문제를 다루는 다수의 부분 문제로 나누기!
  • 1,2,3으로 조합하므로 베이스 케이스로 1,2,3을 설정하고, 이 3개가 어떻게 조합되는지 고민
• 개수를 기준으로 재귀식 구성
  • 경우의 수 '개수'를 세는 것이므로 모든 사례를 확인할 필요가 없음!
  • 습관적으로 모든 사례를 만들어보려 하는데 정말 필요한지 생각해보기
• 동적 프로그래밍
  • 가령, f(4) 값 계산이 반복되므로 저장해두고 나중에 불러와서 사용

접근 방식

• 현재의 문제를 같은 문제를 다루는 다수의 부분 문제로 나누기
  • f(1) = 1
    get_cases(1) >>> [[1]]
  • f(2) = 2
    get_cases(2) >>> [[1,1], [2]]
  • f(3) = 4
    get_cases(3) >>> [[1,1,1], [1,2], [2,1], [3]]
  • f(4) = f(3) + f(2) + f(1)
    • 1 + 3 의 경우 = f(3)
      [[1] + c for c in [[1,1,1], [1,2], [2,1], [3]]]
[[1] + c for c in get_cases(3)]
    • 2 + 2 의 경우 = f(2)
      [[2] + c for c in [[1,1], [2]]]
[[2] + c for c in get_cases(2)]
    • 3 + 1 의 경우 = f(1)
      [[3] + c for c in [[1]]]
[[3] + c for c in get_cases(1)]
  • fn(5) = f(4) + f(3) + f(2) = { f(3) + f(2) + f(1) } + f(3) + f(2)
    • f(4) 값을 저장해두면 중복 계산을 줄일 수 있겠다고 판단
  • fn(N) = f(N-1) + f(N-2) + f(N-3)
    • 일반화

제출 답안

import sys
N = int(sys.stdin.readline())

results = {}

def fn(value):
    if value == 1: return 1
    if value == 2: return 2
    if value == 3: return 4
    if value in results: return results[value]
    total = fn(value-1) + fn(value-2) + fn(value-3)
    results[value] = total
    return total

for i in range(N):
    value = int(sys.stdin.readline())
    print(fn(value))