[Dynamic Programming] 1과 2의 합

문제

정수 n(2<= n<=100)이 주어져있을때 이 n을 1과 2의 합만으로
나타낼 수 있는 방법의 수를 구하시오

 

예를 들어 n=4인 경우는 아래와 같이 5가지이다.
4 = 1+1+1+1
= 2+1+1
= 1+2+1
= 1+1+2
= 2+2

 

 

풀이방법

1을 구할 때

구하는 방식이 1 하나밖에 없으므로, dp[0] = 1로 저장

 

2를 구할 때

구하는 방식은 1+1과 2가 있으므로, dp[1] = 2로 저장

 

3부터 1과 2의 합으로 표현(dp)

3은 1+1+1,1+2, 2+1로 총 3가지가 있는데, 이것을 표현하려고 하면 아래와 같다

• 1 + dp[1] : 방법 2가지
• 2 + dp[0] : 방법 1가지

방식을 모두 더한 결과인 3을 새로운 dp[2]에 저장(dp[2] -> 3을 1이나 2의 합으로 표현하는 경우의수가 들어있음)

 

4를 구할 때

이제 응용하면 4를 구할때 부터는 4는 1+3, 2+2, 3+1가 있는데 이것을 표현하려고 하면 아래와 같다

• 1 + dp[2] : 방법 3가지
• 2 + dp[1] : 방법 2가지

이것을 모두 더하면 5가 나온다

 

이것을 통해 점화식을 세우면

 

dp[n] =  dp[n-2] + dp[n-1]  (n>=2) 인것을 확인할 수 있다. 이제 코드를 통해 표현해 보자

 

코드 구현

python

def count_ways(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

n = int(input())
print(count_ways(n))

 

C++

def count_ways(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

n = int(input())
print(count_ways(n))

 

 

 

참고

출처: https://hyun-am-coding.tistory.com/entry/DP-DP-간단한-문제-백준-1-2-3-더하기-풀기 [현암 코딩:티스토리]