반응형
https://www.acmicpc.net/problem/11052
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
소스코드
풀이
★ 원리를 이해하는 데에는 시간이 오래 걸리지 않았지만 점화식을 세우는 게 조금 난해했던 문제였습니다.
★ DP문제 특성 상 카드를 1개 구매할 때의 최대값부터 n개 구매할 때의 최대값까지를 구해다보면 패턴을 알 수 있습니다.
ex)
arr = [5, 2, 8, 10]
- 카드를 1개 구매할 때 최댓값 => 5
- 카드를 2개 구매할 때 최댓값 => 2 or 10
- 카드를 3개 구매할 때 최댓값 => 8 or 7 or 15
- 카드를 4개 구매할 때 최댓값 =>10 or 13 or 4 or 20
위와 같은 패턴을 보면 n개를 구매할 때 그 앞의 카드팩의 값을 더하여 n을 만들 수 있는 값들 중 최대값을 골라주면 됩니다 !
★ 구현을 할 때는 이중 반복문을 써야합니다. i가 1부터 시작했을 때 j 또한 i까지 반복해야만 해당 카드팩으로 살 수 있는 값을 알 수 있습니다. 따라서 점화식을 세우면 dp[i] = max( dp[i], dp[i-j] + arr[j] ) 형태가 됩니다.
★ dp 배열 안에 인덱스를 기준으로 해당 카드 개수를 구매했을 때 최대값이 들어있습니다.
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 11057번: 오르막 수 (Python) (3) | 2023.08.17 |
|---|---|
| [백준 알고리즘] 13699번: 점화식 (Python) (1) | 2023.08.17 |
| [백준 알고리즘] 2193번: 이친수 (Python) (17) | 2023.08.16 |
| [백준 알고리즘] 25556번: 포스택 (Python) (4) | 2023.08.16 |
| [백준 알고리즘] 27497번: 알파벳 블록 (Python) (0) | 2023.08.16 |