[알고리즘] BOJ 15989번 - 1, 2, 3 더하기 4(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

9 / 50

 

탐색

10 / 50

 

기초 동적 프로그래밍

9 / 50(NEW!)

---

투포인터

2 / 10

 

이분탐색

0 / 10

---

문제

15989번: 1, 2, 3 더하기 4

→ solved.ac 기준 실버 1

---

문제 해결 아이디어

동전 1의 하위 호환 문제.

→ 1부터 MAX 값에 대하여

1을 포함하는 경우의 수, 1과 2를 포함하는 경우의 수, 1과 2, 3을 포함하는 경우의 수를 순서대로 구한다.

⇒dp[j] += dp[j-1]

---

구현

내 풀이

import sys
input = sys.stdin.readline

n = int(input())

MAX = 10001
dp = [0 for _ in range(MAX)]
dp[0] = 1
for i in (1, 2, 3):
  for j in range(i, MAX):
    dp[j] += dp[j-i]

for _ in range(n):
  k = int(input())
  print(dp[k])

---

메모

• 걸린 시간: 7분
  
  • 이미 상위 호환을 풀었기 때문에 해결

---

마치며

동전 1할 때 너무 어려웠어서.. 이 문제를 먼저 풀 걸 그랬다.