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

다이나믹 프로그래밍 문제.

재귀로도 해보고 그리디로도 해보는 등 시도를 많이해보고 맞췄다.

 

처음 이 문제를 봤을 때

1. 처음에는 재귀함수를 사용해서 풀었었다.

사용한 재귀함수

카드의 시작번호를 함수에 설정해두고, 수열을 만드는 방식을 사용해서

1,1,1,1 1,1,1,2 1,1,1,3 ... 이런식으로 호출하는데 카드의 총 갯수가 n을 넘지 않는 선에서만 함수를 호출하도록 했다.

결과는 시간초과였다.

따라서 다른 방식으로 시도하려고 했다.

 

2. 두번째는 그리디를 사용해서 풀었다. 카드마다 가성비가 좋은 것을 골라서 그 카드를 최대한 많이사서 갯수를 맞추는 식으로 풀었다.

그리디를 사용한 코드

우선순위 큐를 사용해서 풀었다. 우선순위 큐에서 각

각 수를 입력을 받을때

카드의 갯수가 최대가 됐을 때에 가격에 따라 정렬했다.

예를들어 4개의 카드의 Pi가 각각 1 5 6 7이라면 각각 4 / i를 곱해주면 순차적으로

4, 10, 8, 7이라는 수가 나오고 이는 2장의 카드를 최대한 많이 샀을 때 가성비가 좋다는 말이 된다.

예시 결과들도 다 맞게 나와서 제출했는데 결과는 틀렸습니다였다.

 

이 문제의 그리디 알고리즘의 반례로는

10 1 100 160 1 1 1 1 1 1 1

이 있었다. 만일 내가 푼 방식으로 풀어서 10 / i를 곱해주면 순차적으로

이러한 값들이 나오게 된다.

사실 카드를 최대한 비싸게 10장 사는 방법은 100가격 2장짜리를 2번사고, 160가격 3장짜리를 2번사서

520가격이 나오는 것인데,

그리디 알고리즘을 쓰면 3장짜리를 이미 3번 사버리기 때문에 2장짜리를 사지 못하게 된다.

 

따라서 이 문제는 DP의 BOTTOM UP 방식으로 값을 아래에서 순차적으로 갱신해줘야 한다.

 

문제 풀이

이 문제의 매 값을 어떻게 갱신해야 할지 생각해보았다.

• 1개를 사는 가격의 최대값은 1개를 그냥 사는 것이고,
• 2개를 사는 가격의 최대값은 2개를 그냥 사는 것 vs 1개를 2번 사는 것
• 3개를 사는 가격의 최대값은 3개를 그냥 사는 것 vs 2개를 사는 가격의 최대값 + 1개를 사는 가격의 최대값
• 4개를 사는 가격의 최대값은 4개를 그냥 사는 것 vs 3개를 사는 가격의 최대값 + 1개를 사는 가격의 최대값 vs 2개를 사는 가격의 최대값 x 2
• ...

으로 이루어진다.

즉 2 <= i <= n라고할 때 최대값을 Ai, 원래 값을 Bi라고 한다면

A(1) = B(1)

A(i) = B(i) vs A(i - 1) + A(1) vs A(i - 2) + A(2) vs .... A(1) + A(i - 1)

으로 식을 나타낼 수 있다.

 

그렇다면 코드로 어떻게 구현했는지 살펴보자.

사용한 STL과 변수

먼저 입력받을 n과, 1~n까지의 각 카드의 갯수만큼에 해당하는 값을 담을 vec 벡터를 만들었다.

그리고 1 <= i <= n일 때, 카드 i개를 살 때의 최대값을 저장할 dp 배열도 만들었다.

 

메인함수 - 1

문제에서 입력을 받는 부분이다.

vec배열을 1번부터 쓰기위해 처음에 0이라는 값을 넣어준 것 외에는 특별히 설명할 게 없다.

메인함수 - 2

카드 한 장 사는 것의 최대값은 그냥 한 장을 사는 것이므로 초기화 해준다.

그리고 위에서 본 것처럼 각 카드를 살 수 있는 것의 최대값들을 갱신해준다.

A(i) = B(i) vs A(i - 1) + A(1) vs A(i - 2) + A(2) vs .... A(1) + A(i - 1)

 

이렇게 코드를 짜면 n이 1000이라고 했을 때도 1000 * 1000 = 1,000,000의 시간이므로 시간제한 1초에 걸리지 않는다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인할 수 있다.