BOJ 11052 카드 구매하기

 

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

11052번: 카드 구매하기

 

dynamic programming 시간 분석은 나에게는 너무 어렵다.

시간이 어떻게 바뀌는지 보기 위해 두 가지 코드를 작성했는데 시간 차가 너무 커서 놀랐다.

 

 

0ms 와 232ms !

 

처음 작성한 코드는 아무런 기교가 사용되지 않는다.

채워야할 남은 카드의 수를 r 이라 했을 때,

이 r 장의 카드를 구성하기 위해 1 번 팩, 2번 팩, ... , n 번 팩을 사용하고 다시 남은 카드에 대한 문제로 축소시켜 간다.

이게 0 ms !?

 

#include<bits/stdc++.h>

using namespace std;

int arr[10001], dp[1001];

int recur(int r){
    if(r==0) return 0;
    
    int &ans=dp[r];
    if(ans) return ans;
    
    for(int i=1;i<=r;i++)
        ans=max(ans, recur(r-i)+arr[i]);
    
    return ans;
}

int main(){
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d", &arr[i]);
    
    printf("%d\n", recur(n));
}

 

이번에는 cutting 을 해보자.

 

위의 코드는  

1번 팩->2번 팩 순으로 사용한 것과 2번 팩->1번 팩 순으로 사용한 것이 같은 결과임에도 다른 경로로 계산한다.

그래서 순서를 강제해 보았다. 

어떤 순간 2번 팩을 사용한 시점부터는 2번 이상의 번호에 해당되는 팩만을 사용하도록,

즉 팩 번호가 증가순으로 사용되도록 했다. 변수 p 는 팩 번호를 나타내는 변수로 사용했다.

 

이 경우 일차원 dp 가 2 차원 dp 가 되니 고려해야할 상태(부분 문제)의 개수가 늘어나지만,

loop 가 줄어들기 때문에 시간은 엇비슷하리라 짐작했는데 어림도 없었다.

다음 코드는 232 ms 가 나왔다.

 

#include<bits/stdc++.h>

using namespace std;

int arr[10001], dp[1001][1001];

int recur(int r,int p){
    if(r==0 || r<p) return 0;
    
    int &ans=dp[r][p];
    if(ans) return ans;
    
    for(int i=p;i<=r;i++)
        ans=max(ans, recur(r-i,i)+arr[i]);
    
    return ans;
}

int main(){
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d", &arr[i]);
    
    printf("%d\n", recur(n, 1));
}

 

차이가 너무 나니까 어찌할 바를 모르겠다.

언제 시간을 투자해서 깊이 있게 시간 복잡도를 분석하는 것을 공부해 보아야겠다.

(아! 정말 dp 시간 분석을 정교하게 할 능력이 있었으면 좋겠다.)