https://www.acmicpc.net/problem/2294
2294번: 동전 2
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주
www.acmicpc.net
소스코드
풀이
다이나믹 프로그래밍으로 해결할 수 있는 문제입니다 !
먼저 문제에 k값의 범위가 1 <= k <= 10,000으로 최대 10,000까지 설정할 수 있습니다.
그렇기에 저희는 dy 리스트를 10,001로 초기화하여, k에 10,000이 들어왔을 때 최솟값을 선택할 수 있도록 해줍니다
주어진 예제로 그린 dy리스트는 다음과 같습니다
dy의 인덱스가 해당 동전으로 k를 만들기 위해 몇개의 동전이 필요한지를 보여줍니다 !
for i in range(a,k+1):
dy[i] = min(dy[i],dy[i-a]+1)
이 코드가 최솟값을 찾아나가는 코드인데, a에는 입력받은 동전의 가치가 들어가고, i는 a부터 k까지 증가합니다.
예를 들어 a에 3이 들어가면, i는 3,4,5,6,7,8,9,10,11,12,13,14,15로 바뀌고, a는 계속해서 3으로 유지됩니다 !
이러한 방식으로 일정 금액을 만들기 위해 주어진 동전이 몇개가 필요한지를 찾아나가며, 최솟값을 찾았을 때 최솟값이 기존 값이 아닌 새로운 값이 된다면 그 값에 +1을 해줘서 동전의 수를 하나씩 늘려줍니다 !
DP 문제는 머리로 생각만 하기엔 해결하기에 조금 어려움이 있는 거 같습니다 !
계속해서 그려보며 이해하는 것이 문제를 빠르게 해결하는 데에 있어서 도움이 될 거 같습니다 :)
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 1764번: 듣보잡 (Python) (0) | 2023.04.06 |
|---|---|
| [백준 알고리즘] 2252번: 줄 세우기 (Python) (0) | 2023.04.05 |
| [백준 알고리즘] 1010번: 다리 놓기 (Python) (0) | 2023.04.04 |
| [백준 알고리즘] 11722번: 가장 긴 감소하는 부분 수열 (Python) (0) | 2023.04.03 |
| [백준 알고리즘] 11053번: 가장 긴 증가하는 부분 수열 (Python) (0) | 2023.04.03 |