[Baekjoon Online Judge] 백준 11052번 카드 구매하기(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 11052번 카드 구매하기

(C++, Python)

(글쓴날 : 2020.04.17)

 

---

* Baekjoon Online Judge, 백준 11052번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 11052번 카드 구매하기

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

가격이 다른 N개만큼의 카드팩이 주어지고, 각 카드팩에는 인덱스만큼의 카드가 들어있을 때 N개의 카드를 갖기 위해 지불해야 하는 최대 금액을 구하는 문제입니다.

 

저의 경우, 동적 계획법을 적용하였으며, C++과 Python을 사용했습니다.

동적 계획법을 위한 점화식은 제 Python 코드 기준 memoiztaion[i][j] = prices[j] + max(memoiztaion[i - j])이며, C++의 경우 max() 대신 max_element()를 사용하였습니다.

이후 memoization을 위한 2차원 테이블을 만든 뒤, 해당 점화식을 적용한 반복문을 돌려 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int memoization[1001][1001];
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N = 0;
    cin >> N;
 
    int prices[1001] = {
        0,
    };
    for (int i = 1; i < N + 1; i++)
        cin >> prices[i];
 
    for (int i = 1; i < N + 1; i++)
        for (int j = 1; j < i + 1; j++)
            memoization[i][j] = prices[j] + *max_element(memoization[i - j], memoization[i - j] + (i - j + 1));
 
    cout << *max_element(memoization[N], memoization[N] + (N + 1));
 
    return 0;
}

---

* Python 코드(PyPy3)

import sys
input = sys.stdin.readline
 
N = int(input())
prices = [0] + list(map(int, input().split()))
memoiztaion = [[0] * (N + 1) for _ in range(N + 1)]
 
for i in range(1, N + 1):
    for j in range(1, i + 1):
        memoiztaion[i][j] = prices[j] + max(memoiztaion[i - j])
        
print(max(memoiztaion[-1]))

---