[백준 11052] 카드 구매하기(C++)

카드 구매하기

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

 

문제 해결 과정

1. 문제를 읽고 이해하기

N개의 카드 팩이 있고 입력값의 순서에 따라 i 장의 카드가 들어있다.

N장의 카드를 얻기 위해 지불해야 하는 카드 값의 최댓값을 구하라.

 

N이 4이고 1, 5, 6, 7이 각 카드 팩의 가격으로 주어졌다면

 

1장 팩 가격: 1

2장 팩 가격: 5

3장 팩 가격: 6

4장 팩 가격: 7

 

카드의 수가 4장이 되는 모든 경우의 수의 가격을 살펴보자. 편의상 N장의 카드가 담긴 팩을 팩N, 값단위를 $로 표기하겠다.

팩1 * 4개 = 4$

팩1 * 2개 + 팩2 = $7

팩2 * 2 = $10

팩3 + 팩1 = $7

팩4 = $7

 

∴ 4장을 구매하기 위한 최댓값은 2장 팩을 2개 구매하는 것이다.

2. 재정의와 추상화

어느정도의 본질만 남겨두고 축약하여 다루기 쉽게 표현해야 한다.
어떤 부분을 추상화할 지를 선택하는 작업과 문제를 재정의 하는 방법들에 대한 고찰을 해야한다.

 

예제에서 보았다시피 N에 해당하는 최댓값을 구하기 위해서는 경우의 수를 구해야 한다.

각 경우의 수를 구한 뒤에는 그 중 최댓값을 선택해서 출력해야 한다.

3. 계획 세우기

경우의 수 구하기

각 N에 대해서 가질 수 있는 값들을 나열해서 규칙성을 파악해보자.

뭔가 규칙성이 있을 것 같다.

K은 K - 1에서 1을 더하고 K - 2에서 2를 더하고 중복값을 제거, 본인을 더하면 모든 경우의 수를 발견할 수 있다.

경우의 수의 개수를 구하는 문제는 아니기 때문에 개수에 대한 규칙성은 버려두자.

각 조합의 수를 오름차순 + 사전 순으로 정렬하고나서 문제를 어떻게 접근할지 고민해보자.

 

5의 경우를 보면 아래의 7개의 경우의 수가 있다.

1: 5

2: 41

3: 32

4: 311

5: 221

6: 2111

7: 11111

 

각 첫째 자릿수를 보면 그 뒤에 오는 수는 현재 K에 대하여 K - 첫째 자릿수에 대한 경우의 수임을 볼 수 있다.

5를 기준으로 첫 번째 수와 나머지로만 보았을 때 (5, 0) / (4, 1) / (3, 2) / (2, 3) / (1, 4)의 경우의 수가 있다.

5를 2로 나눈 2보다 작은 값으로 시작하는 경우인 (2, 3) / (1, 4)은 중복된다.

(5, 0) / (4, 1) / (3, 2)의 최댓값을 구할 수 있으면 된다.

 

Bottom up DP로 최댓값 구하기

1부터 각 최댓값을 구해놓으면 5에서 (5, 0) / (4, 1) / (3, 2) 의 값을 카드값[5], 최댓값[4] + 최댓값[1], 최댓값[3] + 최댓값[2] 에서 3번의 비교로 구할 수 있다.

이 풀이에 기초해서 테이블과 초기값, 점화식을 살펴보자.

테이블

각 K에 해당하는 최댓값을 저장할 int 배열 T

초기값

1은 카드값[1]

점화식

K는 시작하는 수 i에 대해서 K/2보다 같거나 클 때까지 [i] + [K - i]를 조회하여 가장 큰 값을 저장한다.

T[K] = packs[K];
for(int i = K - 1; i >= K / 2; --i) 
	T[K] = max(T[K], T[i] + T[K - i]);

4. 계획 검증하기

- 시간 제한: 1초

- 메모리 제한: 256MB

- 구하려는 카드 개수 N의 최댓값: 1000

- 카드팩의 값 P의 최댓값: 10,000

 

시간 제한에 따른 알고리즘 선택

풀이는 O(N^2)이나, 최댓값을 고려해보아도 1000^2는 100만으로 1초(약 1억회 연산)에 충분히 들어온다.

 

값의 범위에 따른 자료형 선택

수의 합이 가질 수 있는 가장 큰 값은 천만(10,000 * 1,000)으로 int 범위 이내이기 때문에 반환할 자료형은 int로 충분하다.

input을 저장할 int 배열 packs[1001], 최댓값을 저장할 int 배열 T[1001] 8KB가 필요하다.

코드

#include <bits/stdc++.h>

using namespace std;
int N;
int packs[1001];
int T[1001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> packs[i];
    }
    T[1] = packs[1];

    for (int i = 2; i <= N; ++i) {
        int max_val = packs[i];
        for (int j = i - 1; j >= i/2; --j) {
            max_val = max(max_val, T[j] + T[i - j]);
        }
        T[i] = max_val;
    }
    cout << T[N];
}

※ 오류나 개선점이 있다면 알려주세요 :) 신속히 수정하겠습니다.