[Baekjoon 9095 / Python / 실버3] 1, 2, 3 더하기

문제

import sys

input = sys.stdin.readline

N = int(input())

def plus(num):

    if num == 1:

        return 1

    elif num == 2:

        return 2

    elif num == 3:

        return 4

    else:

        return plus(num-1) + plus(num-2) + plus(num-3)

for _ in range(N):

    print(plus(int(input())))

 

재귀 방식( 바람직하지 않음 )

 

DP문제다. 두가지 방식으로 풀어보았다. 하나는 재귀 방식, 하나는 DP테이블을 사용하는 방식.

이해를 하긴 했으나 뭔가 와닿지가 않는다. 아 이런거구나~ 하고 이해해놓고 잠시 뒤에, 근데 이게 왜 이렇게 되지....? 계속 반복이다. 

 

4를 만드는 경우의 수를 구한다고 생각해 보자. 사용할 수 있는 숫자는 1,2,3 뿐이다.

그렇다면, 일단 "4"라는 숫자는 어떻게 만들어지는지 생각해 보자. 1, 2, 3 밖에 못 쓰니까 (1 + 1), (2 + 2), (3 + 1) 이렇게 세 가지가 있겠다. 이렇게 세가지로밖에 만들 수 없다. 이게 전부다.

 

그렇다면 숫자 1, 2, 3이 만들어지려면 각각 몇 개의 경우의 수를 가지는가? 1은 1, 2는 2, 3은 4개다.

1 경우의 수 : 1개 -> 1개의 경우의 수에 3을 더하면 4가 만들어진다. ( 4를 만드는 경우의 수 1개 )

2 경우의 수 : 2개 -> 2개의 경우의 수에 각각 2를 더하면 4가 만들어진다. ( 4를 만드는 경우의 수 2개 )

3 경우의 수 : 4개 -> 4개의 경우의 수에 각각 1을 더하면 4가 만들어진다. ( 4를 만드는 경우의 수 4개 )

이 세가지 경우의 수를 모두 더하면 (1 + 2 + 4) 7이 되고, 7이 4를 만드는 모든 경우의 수이다.

즉 점화식은 dp[N] = dp[N-1] + dp[N-2] + dp[N-3] 이 되겠다.

 

여기서 -1, -2, -3까지만 가는 이유는 당연히 우리는 숫자를 1, 2, 3밖에 쓰지 못하기 때문이다.

 

import sys

input = sys.stdin.readline

N = int(input())

# 숫자와 인덱스를 맞추기 위해 1을 더한 11로 한다 ( 숫자범위 : 1 ~ 10 )

dp = [0] * 11

dp[1] = 1

dp[2] = 2

dp[3] = 4

for i in range(4, len(dp)):

    dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

for _ in range(N):

    print(dp[int(input())])

 

DP테이블을 사용하는 방식( 바람직함 )

 

이 문제는 입력으로 들어오는 N의 크기가 1~10 밖에 되지 않기 때문에 연산횟수와 성능이 크게 차이나지 않는다. 그러나 N이 조금만 더 커져도 두 코드의 성능차이는 극명하게 갈릴 것이다. 재귀 방식은 점화식을 사용하긴 했으나 DP방식이라고 보긴 어렵다. 재귀함수를 사용해서 불필요한 동일한 연산을 반복적으로 실행하기 때문이다.

 

두번째는 동일한 연산을 다시 수행하지 않고 이전의 결과값을 재활용함으로써, 정석적인 DP방식을 통해 효율적으로 문제를 해결한다.