[BOJ/백준] 16194 카드 구매하기 2

● [문제번호 16194] 카드 구매하기 2

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

16194번: 카드 구매하기 2

 

● 알아야 할 것

: 다이나믹 프로그래밍

: vector 자료구조와 메소드

 

● 풀이 과정

: 이전에 풀었던 [11052 카드 구매하기] 문제에서 max → min 으로 변경하기만 하면 된다.

 

1. 테이블 정의

→ 각 index의 값은 카드 index개를 갖기 위해 지불해야 하는 금액의 최솟값을 나타낸다.

 

2. 점화식 찾기

→ dp[i] = min(dp[i - j] + dp[j], dp[i])

 

dp[i - j] 와 dp[i] 에는 각 index까지 오는 방법 중 최솟값을 가지고 있으므로

예를들어 dp[i]에서 dp[1] 이 i 개 있는 상황은 고려하지 않아도 된다.

 

3. 초기값 정하기

기존에 입력한 값들을 가지고 다이나믹 프로그래밍을 실행한다.

 

● 주의 할 것

: NULL

 

● 참고 할 것

: [11052 카드 구매하기] 문제

https://pirateturtle.tistory.com/203

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

vector<int> P;
int N;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    P.assign(N + 1, 0);
    
    // 입력
    for(int p = 1; p <= N; p++)
        cin >> P[p];
    
    // 카드 i개를 갖기 위해 지불해야 하는 금액의 최솟값 = P[i]
    for(int i = 1; i <= N; i++)
        for(int j = 1; j < i; j++)
            P[i] = min(P[i - j] + P[j], P[i]);
    
    // 출력
    cout << P[N];
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [400 - 다이나믹 프로그래밍 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1463	1로 만들기	https://pirateturtle.tistory.com/199
2	11726	2×n 타일링	https://pirateturtle.tistory.com/200
3	11727	2×n 타일링 2	https://pirateturtle.tistory.com/201
4	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/202
5	11052	카드 구매하기	https://pirateturtle.tistory.com/203
6	16194	카드 구매하기 2	https://pirateturtle.tistory.com/204
7	15990	1, 2, 3 더하기 5	https://pirateturtle.tistory.com/205
8	10844	쉬운 계단 수	https://pirateturtle.tistory.com/206
9	2193	이친수	https://pirateturtle.tistory.com/207
10	11053	가장 긴 증가하는 부분 수열	https://pirateturtle.tistory.com/208
11	14002	가장 긴 증가하는 부분 수열 4	https://pirateturtle.tistory.com/209
12	1912	연속합	https://pirateturtle.tistory.com/210
13	1699	제곱수의 합	https://pirateturtle.tistory.com/211
14	2225	합분해	https://pirateturtle.tistory.com/212