BOJ 2629 양팔 저울

www.acmicpc.net/problem/2629

2629번: 양팔저울

 

예전에 학교에서 풀었던 거스름돈 문제(거스름돈 단위들의 최대 공약수가 1)와 매우 유사했다.

단, 이 문제는 반대쪽에서도 거스름돈을 제시하여 가격을 맞출 수 있다는 조건이 추가되었다고 생각하였다. 마치 현실에서  6000원 어치를 샀는데, 사장님이 1000원짜리는 없고 5000원 짜리만 있어서 우리가 11000원을 주고 5000원을 거슬러 받는 경우랑 유사하다고 생각하였다.

이에 따른 점화식은 다음과 같다.

DP[i][j] = DP[ i-cost[ j ] ][ j-1 ] |  DP[ i ][ j-1 ] | DP[ |i-cost[ j ]| ][ j-1 ] 

(DP[ i - cost[j] | ][ j-1 ] 부분이 추가되었다 )

 

처음엔 기존 점화식에 추가작업을 하여 문제를 풀려했지만, 오히려 동작이 명확하지 않아서 점화식을 세워 풀게 되니 바로 통과하였다..

DP는 점화식이 중요한 것 같다.

 

코드는 다음과 같다.

#include <cstdio>
#include <cmath>



int arr[30];
bool dp[16001][30];
int r,T;



int main(){
    scanf("%d",&r);

    int total = 0;

    for(int i=0;i<r;i++) {
        scanf("%d",arr+i);
        dp[arr[i]][i] = true;
        total += arr[i];
    }

    for(int j=1;j<r;j++){
        for(int i=15000;i>=1;i--){  

            dp[i][j] |= dp[i][j-1];
            dp[i][j] |= dp[i+arr[j]][j-1];
            dp[i][j] |= dp[std::abs(i-arr[j])][j-1];
            
        }
    }
    
    
  
    
    
    scanf("%d",&T);
    while(T--){
        int t; scanf("%d",&t);
        if(t <= total)
            printf("%c ", dp[t][r-1] ? 'Y': 'N');
        else
            printf("N ");

    }


    return 0;
}