[Python] 백준 9095 1, 2, 3 더하기 | DP

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

 

문제 해결 포인트

- DP(다이나믹 프로그래밍)의 전형적인 문제이다

- DP는 한번 진행한 계산에 대해서 저장 해두고 또 발생시 계산 값만 사용한다.

- 해당 코드에서 numbers 배열은 계산 결과 값을 저장해두는 역할을 한다.

 

- 1, 2, 3을 이용하여 1, 2, 3을 만드는 방법을 생각해보자

 

1 = 1

1을 만드는 방법은 1개(numbers[1] = 1)

 

2 = 1 + 1

2 = 2

2를 만드는 방법은 2개(numbers[2] = 2)

 

3 = 1 + 1 + 1

3 = 1 + 2

3 =  2 + 1

3 = 3

3을 만드는 방법은 4개(numbers[3] = 4)임을 알 수 있다.

 

- 그렇다면 4는 앞서 구한 계산을 활용하여 어떻게 구할 수 있을까?

 

4 = 1 + 3

 

4 = 1 + 1 + 2

4 = 2 + 2

 

4 = 1 + 1 + 1 + 1

4 = 1 + 2 + 1

4 = 2 + 1 + 1

4 = 3 + 1

 

규칙성을 찾으셨나요?! 그렇다면 당신은 천재👏

 

 

 

4를 만들 수 있는 경우의 수는

1을 만들 수 있는 경우에 모두 3을 더하면 만들 수 있고

2를 만들 수 있는 경우에 모두 2를 더하면 만들 수 있고

3을 만들 수 있는 경우에 모두 1을 더하면 만들 수 있습니다.

 

결국 numbers[1] + numbers[2] + numbers[3] = numbers[4]가 되는 것입니다.

 

이를 표준화 하면 ' a > 3'일 때, numbers[a] = numbers[a-3] + numbers[a-2] + numbers[a-1] 이 됩니다

 

 

작성 코드

import sys
input = sys.stdin.readline

# 각 인덱스 값을 만들 수 있는 개수 저장
# 1은 1개, 2는 2개, 3은 4개의 만들 수 있는 조합이 존재 함
numbers = [0, 1, 2, 4] + [0]*7  
n = int(input())

for i in range(4, 11):
    numbers[i] = numbers[i-3] + numbers[i-2] + numbers[i-1]  # 점화식

# print(numbers)   # [0, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274]

for i in range(n):
    m = int(input())  # 각 요구 값의 (만들 수 있는) 개수 반환
    print(numbers[m])

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

 

---

REFERENCE

https://hyun-am-coding.tistory.com/entry/DP-DP-%EA%B0%84%EB%8B%A8%ED%95%9C-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0-%ED%92%80%EA%B8%B0