[BOJ] 1, 2, 3 더하기


  • BOJ의 1, 2, 3 더하기 문제 풀이입니다

문제 풀이

  • 해당문제는 Dynamic Programming 문제로써 문제를 작은 문제를 나누고 일정한 규칙을 발견해서 문제를 해결 할 수 있습니다

  • 각 숫자를 만들 수 있는 경우의 수를 보면 다음과 같습니다

  • 1 -> 1 => 1가지

  • 2 -> 2, 1+1, =>2가지

  • 3 -> 3, 1+2, 2+1 1+1+1 => 4가지

  • 4

    • 1 + 1 + 1 + 1 -> 1가지
    • 1 + 1 + 2 -> 3가지
    • 1 + 3 -> 2 가지
    • 2 + 2 -> 2가지
    • => 총 7가지
  • 5

    • 1 + 1 + 1 + 1 + 1 -> 1가지
    • 1 + 1 + 1 + 2 -> 4가지
    • 1 + 1 + 3 -> 3가지
    • 2 + 2 + 1 -> 3가지
    • 2 + 3 => 2가지
    • => 총 13가지
  • 6

    • 1 + 1 + 1 + 1 + 1 + 1가지
    • 1 + 1 + 1 + 1 + 2 -> 5가지
    • 1 + 1 + 1 + 3 -> 4가지
    • 1 + 1 + 2 + 2 -> 6가지
    • 1 + 2 + 3 -> 6가지
    • 2 + 2 + 2 -> 1가지
    • 3 + 3 -> 1가지
    • => 총 24가지
  • 그리고 n번째 숫자의 경우의 수는 n-1, n-2, n-3번째 숫자를 만드는 경우의 수를 총 합친 것을 알 수 있습니다
  • 즉 a[n] = a[n-1] + a[n-2] + a[n-3] 과 같은 식이 성립하는 것을 알 수 있습니다

전체 코드

import sys

def dp(num, lst):
    if num == 1:
        return 1
    elif num == 2:
        return 2
    elif num == 3:
        return 4
    elif lst[num] != 0:
        return lst[num]
    lst[num] = dp(num-1, lst) + dp(num-2, lst) + dp(num-3, lst)
    return lst[num]

N = int(sys.stdin.readline())
num_lst = []
for _ in range(N):
    num_lst.append(int(sys.stdin.readline()))


for num in num_lst:
    lst = [0] * (num+1)
    print(dp(num, lst))




Reference









© 2020. by dkmqflx

Powered by dkmqflx