정올 고급 강의 7~8차시 정리

7차시 동적테이블의 응용2

[색상환 문제]

N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003으로 나눈 나머지 출력

빨간색부터 시작하면 인접한 연지, 주황을 선택 못하게 되니 빨강-> 다홍부터 시작하고 빨간색이 아니라면 주황색부터 하면 됨

탐색함수

solve(a, b)=현재 a번 색상에 대해 고려하는 상태이며, 지금까지 규칙에 맞도록 b개의 색깔을 이미 선택한 상태 -> X

빨간색을 선택하면 나오는 문제를 인식할 수 없음

solve(a, b)=현재 a번 색상에 대해 고려하는 상태이며, 지금까지 규칙에 맞도록 b개의 색깔을 이미 선택했고, c가 참이면 마지막

색을 고를 수 없는 상태

#include <stdio.h>
#include <string.h>
#define MN 1000000003
int n, k, D[2][1010][1010]; //D[can][a][b]-현재 a번 색에 대해서 고려하는 상태로 지금까지 b개의 색을 골랐으며 can이 참이면 마지막 색을 고를 수 없는 상태
 
int sovle(int a, int b, bool can){
    if(b==k) return 1;
    if(a>=n-can) return 0; //아직 k개의 숫자를 못골랐는데 마지막 색에 도달했기 때문에 실패함. can을 n에서 빼서 can이 1일때는 마지막 색을 탐색하지 못한다는 점을 반영
 
    if(D[can[a][b] == -1){
        D[can][a][b] = (f(a+1,b,can)+f(a+2,b+1,can))%MN;
 
        //f(a+2, b+1, can); 고른 경우 색을 두 개 건너뛰고 b++
        //f(a+1, b, can); 고르지 않은 경우 다음 색 탐색
    }
    return D[can][a][b];
}
 
int main(){
    memset(D, -1, sizeof(D)); //채울 배열, 채울 숫자, 배열의 크기-배열을 특정 값으로 전부 채움
    scanf("%d %d", &n, &k);
    printf("%d", (f(1,0,0) + f(2,1,1)%MN);
    return 0;
}
 
//나머지 처리할 때 10억~개를 3번이상 더하면 더하는 순간 오버플로우기 때문에 ((a + b %MN)+C) %MN 이런식으로

점화식 설계

#include <stdio.h>
#define MN 1000000003
 
int D[1001][1001];
 
int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i=2;i<=n;i++){
        for(int j=1; j<=n/2;j++){
            if(j==1) D[i][j]=i;
            else D[i][j]=(D[i-2][j-1]+D[i-1][j])%MN);
        }
    }
    printf("%d\n", D[n][k]);
    return 0;
}
 

8차시 동적테이블의 응용3

[선물]

길동이는 세 쌍둥이의 첫째, 실순 둘째, 길삼 막내

생일을 맞아 받은 선물을 나눠갖는다

조건1: 각자의 부피는 길동>=길순>=길삼을 만족하도록 분배

조건2: 다음의 d가 최소가 되도록 한다. d=길동선물의 부피합 - 길삼선물의 부피합 (서로 최대한 공평하게 나눠갖는다는 의미)

조건3: 같은 d가 되는 배분 방법이 여럿일 경우에는 길동의 선물의 부피 합이 적은 방법을 선택한다

예(선물 6, 4, 4, 4, 6, 9), 길동-12, 길순-12, 길삼-9

12-9=3으로 최소가 됨

(13/10/10으로 배분하는 방법도 있지만 조건3에 의해 불가능)

W=a+b+c

1~k까지의 선물을 받았을 때, 길순이가 부피 b, 길삼이가 부피 c를 받은 상태는 존재하는가?

#include <stdio.h>
 
int n, w, G[21], A, B, C, ans =987654321;
bool D[21][2001][2001];
 
int main(){
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d", G[i]), W+=G[i]);
    }
    
    D[0][0][0] = true; //아무도 선물을 가지지 않은 상태
    for(int i=0;i<n;i++){
        for(int a=0;a<=2000;a++){
            for(int b=0;b<=2000;b++){
                D[i][a][b]=(D[i-1][a][b] || /*길동이가 받았을 때*/
                (a-G[i]<0 ? false : D[i-1][a-G[i]][b]) || /*길순이가 받았을 때*/
                (b-G[i]<0 ? false : D[i-1][a][b-G[i]])); /*길삼이가 받았을 때*/
            }
        }
    }
    for(int a=0;a<=2000;a++){
        for(int b=0;b<=2000;b++){
            if(D[n][a][b]){
                if(W-(a+b)>=a && a>=b && W-(a+b) -b<=ans){ //조건 1, 2
                    ans = W-(a+b)-b;
                    A = W-(a+b);
                    B=a;
                    C=b;
                }
            }
        }
    }
    printf("%d %d %d\n", A, B, C);
    return 0;
}
 

 

//배열 아껴서 메모리 줄이기

#include <stdio.h>
 
int n, w, G[21], A, B, C, ans =987654321;
bool D[2][2001][2001]; //i-1값만 참고하기 때문에 21일 필요 없음
 
int main(){
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d", G[i]), W+=G[i]);
    }
    
    D[0][0][0] = true; //아무도 선물을 가지지 않은 상태
    for(int i=0;i<n;i++){
        for(int a=0;a<=2000;a++){
            for(int b=0;b<=2000;b++){
                D[i%2][a][b]=(D[(i-1)%2][a][b] || /*길동이가 받았을 때*/
                (a-G[i]<0 ? false : D[(i-1)%2][a-G[i]][b]) || /*길순이가 받았을 때*/
                (b-G[i]<0 ? false : D[(i-1)%2][a][b-G[i]])); /*길삼이가 받았을 때*/
            }
        }
    }
    for(int a=0;a<=2000;a++){
        for(int b=0;b<=2000;b++){
            if(D[n%2][a][b]){
                if(W-(a+b)>=a && a>=b && W-(a+b) -b<=ans){ //조건 1, 2
                    ans = W-(a+b)-b;
                    A = W-(a+b);
                    B=a;
                    C=b;
                }
            }
        }
    }
    printf("%d %d %d\n", A, B, C);
    return 0;
}