[C/C++] 11052: 카드 구매하기

11052: 카드 구매하기 문제

 

문제를 Top-down 방식으로 이해해본 다음에 Bottom-Up 방식으로 구현을 하였다.

예를 들어 dp[n]을 구하는 경우에

dp[n]=max(dp[n]+dp[0],dp[n-1]+dp[1],dp[n-2]+dp[2],,,,,,,,,,dp[n-k]+dp[k],,,,) 형태가 된다는 것을 알 수 있다.

이때 dp[n-k]와 dp[k]일때 (n-k>=k) 최대값을 각각 구하고 있다면 dp[n-k]+dp[k]도 최댓값이 된다.

따라서 k=1에서 k=[n/2]인 자연수까지 중에서 최댓값을 구한다면 dp[n]을 구할 수 있게 된다.

 

그 결과 dp[1]부터 dp[n]까지 각 경우의 최댓값을 dp배열에 저장하고 이를 이용해 문제를 풀었다! 

이걸 비교하는 코드는 아래와 같다.

for(int i=2;i<=n;i++)
      {        
        int max=0,j=0;
        while(i-j>=j)
          {
            dp[i]=dp[i-j]+dp[j]>dp[i]?dp[i-j]+dp[j]:dp[i];
            j++;           
          }
      }

특히 이전코드에서 arr[i]를 dp[i]에 복사하여 dp배열을 초기화했으므로

dp[i]=dp[i-j]+dp[j]>dp[i]?dp[i-j]+dp[j]:dp[i]; 코드를 통해 i>=2*j일때 dp[i]의 최댓값을 구할 수 있었다.

 

밑에는 전체 소스코드이다!!

#include <stdio.h>
#include <string.h>

int arr[1001];
int dp[1001];

int main(void)
  {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      {
        scanf("%d",&arr[i]); 
        dp[i]=arr[i]; //dp배열을 arr배열을 복사하여 초기화
      }
    
    for(int i=2;i<=n;i++)
      {        
        int max=0,j=0;
        while(i-j>=j)
          {
            dp[i]=dp[i-j]+dp[j]>dp[i]?dp[i-j]+dp[j]:dp[i];
            j++;           
          }
      }      
      printf("%d",dp[n]);
   
  }