[알고리즘] BOJ 2293번 - 동전 1(python3)

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

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

---

Greedy

9 / 50

 

탐색

10 / 50

 

기초 동적 프로그래밍

8 / 50(NEW!)

---

투포인터

2 / 10

 

이분탐색

0 / 10

---

문제

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

2293번: 동전 1

→ solved.ac 기준 골드 5

---

문제 해결 아이디어

문제의 예제처럼 수중에 1원, 2원, 5원이 있다고 가정했을 때 10원을 구하기 위한 경우의 수?

⇒ 해당 문제는 실제로 큰 문제를 작은 문제로 나눌 수 있으므로 dp 문제.

⇒ 가지고 있는 동전을 순서대로 접근해서 해당 동전을 포함시켰을 때 경우의 수 dp를 구하자.

⇒ 1원을 포함한 경우의 수

dp[1] = dp[2] = dp[3] = dp[4] = ... = dp[10] = 1

⇒ 1, 2원을 포함한 경우의 수

2원을 포함시키지 않는 경우: dp[1]

2원을 포함하는 경우:

1) dp[2] → 1 + 1, 2

2) dp[3] → 1 + 1 + 1, 1 + 2

3) dp[4] → 1 + 1 + 1 + 1, 1 + 1 + 2, 2 + 2

4) dp[5] → 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 2, 1 + 2 + 2

//...

⇒ j원을 포함하는 경우의 수는 다음과 같은 점화식을 갖는다.

dp[i] = dp[i] + dp[i-j]

---

구현

내 풀이

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
values = [int(input()) for _ in range(n)]

dp = [0 for _ in range(k + 1)]
dp[0] = 1

for value in values:
  for i in range(value, k + 1):
    dp[i] += dp[i-value]
    
print(dp[k])

---

메모

• 해당 부분은 1트 만에 못 풀고 다른 사람 풀이를 참고했기 때문에 다음에 한 번 더 풀어봐야 함..

---