https://www.acmicpc.net/problem/16194
[필자 사고]
동적프로그래밍을 이용해야 푸는 문제다.
필자는 bottom-up 방식을 이용하여 해당 문제를 해결 했다.
해당 문제를 풀면서 어려움에 처했던 점은 min값을 비교할 때
arr[i]의 자체의 값은 비교 대상에서 제했던 점이다.
arr[i]의 자체값을 dp값과 비교하기 위해 dp[0]을 0으로 초기화 후 문제를 풀었다.
아래는 자세한 코드 해설이다.
[코드 해설]
1. 프로그램 개요
이 프로그램은 동적 프로그래밍(DP) 을 이용하여 최소 비용으로 N까지 도달하는 방법을 계산하는 문제를 해결한다.
입력으로 주어진 arr[i]는 i 크기의 카드팩을 구매하는 비용이며,
이 프로그램은 카드 N개를 구매하는 최소 비용을 구하는 문제를 해결한다.
2. func(int idx) 함수 (최소 비용 갱신)
이 함수는 동적 프로그래밍 점화식을 사용하여 dp[idx] 값을 갱신한다.
- dp[idx]는 카드 idx개를 구매하는 최소 비용을 의미한다.
- dp[idx] 값은 이전 값(dp[idx - i])과 현재 카드팩(arr[i])을 더한 값 중 최소값을 선택한다.
즉,
dp[idx]=min(dp[idx],dp[idx−i]+arr[i])dp[idx] = \min(dp[idx], dp[idx - i] + arr[i])
를 반복하여 최적의 값을 찾는다.
3. 동적 프로그래밍을 이용한 최소 비용 계산 (Game_Start 함수)
- N 값을 입력받는다.
- dp 벡터를 크기 N+1로 초기화하고, 최댓값(99999999) 으로 설정하여 최소값을 찾을 수 있도록 한다.
- arr[i]를 입력받아 카드팩 가격을 저장한다.
- dp[0] = 0, dp[1] = arr[1]으로 초기값 설정
- func(i)를 호출하여 dp[i] 값을 갱신한다.
- 최종적으로 dp[N] 값을 출력한다.
4. 결과 출력
- dp[N] 값을 출력하며, 이는 N개의 카드를 구매하는 최소 비용을 나타낸다.
5. 전체 코드 흐름 요약
- N을 입력받는다.
- 카드팩 가격을 입력받아 arr[i]에 저장한다.
- DP를 활용하여 최소 비용을 계산
- 결과를 출력한다.
[소스 코드]
#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;
int N;
vector<int> dp;
vector<int> arr;
void func(int idx) {
for (int i = 1; i <= idx; i++) {
dp[idx] = min(dp[idx - i] + arr[i], dp[idx]);
}
}
void Game_Start() {
cin >> N;
dp.resize(N + 1,99999999);
arr.resize(N + 1);
for (int i = 1; i <= N; i++) {
cin >> arr[i];
}
dp[0] = 0;
dp[1] = arr[1];
for (int i = 2; i <= N; i++) {
func(i);
}
cout << dp[N];
}
int main(void) {
Game_Start();
}