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

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

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

11052번: 카드 구매하기

 

● 알아야 할 것

: 다이나믹 프로그래밍

: vector 자료구조와 메소드

 

● 풀이 과정

: 점화식을 찾을 듯 말 듯한 고통 속에 결국 구글링을 했다.

뭔가 예전에 이러한 방식과 비슷한 문제를 본 것 같은데 다음에 다시 만나게 되면 풀 수 있도록 연습해 둬야겠다.

 

1. 테이블 정의

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

 

2. 점화식 찾기

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

 

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

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

(즉, 아래 그림에서 빨간 테두리이외의 경우의 수는 빨간 테두리에 포함되어 있으므로 고려하지 않아도 된다.)

 

3. 초기값 정하기

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

 

빨간 테두리만 고려하면 된다 / 최종 결과는 파란 테두리

● 주의 할 것

: NULL

 

● 참고 할 것

: 코드 참고

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/11052.cpp

 

● 풀이 코드

#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] = max(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