[알고리즘][11][백준_1029][C언어] - 그림교환

 

---

알고리즘 설계

문제에서 주어지는 n명의 그림 소유상태를 비트마스킹으로 표현하고 DP를 이용해서 해결할수 있는문제이다.

 

만약 비트연산을 처음 들어봤다면 비트연산을 먼저 공부하고 오는 것을 추천한다.

 

전체 코드는 다음과 같다.

 

#include <stdio.h>

int n;

int pp[16][16];
int dp[15][32768] = {0};
int ddp(int state, int before, int price);
int max(int x, int y);


int main(){
    int i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            scanf("%1d",&pp[i][j]);
        }
    }    
    printf("%d",ddp(1,0,0)+1);

}

int ddp(int state, int before, int price){
    printf("state : %d\n",state);
    int i,j;
    int tmp1, tmp2;
    int maximum = 0;
    if(state == (1<<n)-1){ // 모든 사람이 그림을 소유했거나 소유하고있으면 정상적으로 종료
        return 0;
    }

    if(dp[before][state] != 0){
        return dp[before][state];
    }
    for(i=1;i<n;i++){
        if((state & (1<<i)) == 0 && pp[before][i] >= price){
        // i번째 사람이 그림을 소유한적이 없다 && 이전사람에서 i번째사람한테 파는 가격이 
        // 이전에 판 가격보다 같거나 높다
            maximum = max(maximum,1+ddp(state+(1<<i),i,pp[before][i]));
        }
    }
    dp[before][state] = maximum;
    return maximum;
}

int max(int x, int y){
    return x > y ? x : y;
}

 

 

비트 마스킹은 오른쪽부터 1번째 사람으로 정할수도 있고 왼쪽부터 1번째사람이라고 정할수도 있는데 본인이 편한 쪽으로 하면된다.

 

이 코드에서는 맨 오른쪽부터 1번째 사람으로 고정했다.

 

따라서 만약 n = 5 라면 초기 값이 00001, 즉 1로 시작하게된다.

 

맨 처음사람도 그림을 소유했던 사람에 속하기 때문이다.

 

예를들어 첫번째사람이 두번째사람에게 그림을 주었고 두번째 사람이 다섯번째 사람에게 그림을 주었다면

 

현재 상태는 10011이 된다.

 

따라서 처음에 함수를 실행할때 state 부분에 1을 넣고 시작한다.

printf("%d",ddp(1,0,0)+1);

 

 

그 다음은 그림을 판매할 다음 사람을 선택하는 부분인데 

1. 구매자는 그림을 소유한적이 없었어야 한다.

2. 현재소유자->구매자 판매가격이 이전의 판매가격보다 크거나 같아야한다.

이 두가지 조건을 동시에 만족하는 사람에게만 판매할수 있고 그 부분이 아래 if문으로 표현되어있다.

 

여기서 

state : 현재 그림 소유상태 (ex 10101, 10111 ...)

before : 이전에 그림을 소유했던 사람의 인덱스

price : 이전 거래에서 판매되었던 가격

을 의미한다.

int ddp(int state, int before, int price){

    int maximum = 0;
	
    ...
    
    for(i=1;i<n;i++){
        if((state & (1<<i)) == 0 && pp[before][i] >= price){
            maximum = max(maximum,1+ddp(state+(1<<i),i,pp[before][i]));
        }
    }

    return maximum;
}

 

그리고 마지막으로 dp배열을 이용해서 인덱스가 before번째인사람이 판매해야하는 상황에서 그림소유 상태가 state 일때 값을 메모이제이션 해두면된다.

int ddp(int state, int before, int price){
    if(dp[before][state] != 0){
        return dp[before][state];
    }
    
    ...
    
    dp[before][state] = maximum;
    return maximum;
}