[백준] 2629 양팔저울

Posted on | In

방학 때 또 1일1커밋을 해보기 위해서 오랜만에 블로그를 잡았다! 꼬박꼬박 공부해서 문제를 다 잘 풀 수 있었으면 좋겠다.

문제 설명

링크 이 문제는 평범한 배낭과 비슷한 냅색 문제라고 한다! 냅색 문제가 기억이 안나서 다시 보고 왔다.. ㅎㅎ 시간이 나면 평범한 배낭 문제도 포스팅 해봐야 겠다! 어쨌든 이 문제는 양팔 저울에 추랑 구슬을 올려서 구슬 무게를 맞출 수 있는지를 묻는 문제이다. 추의 개수와 각 추의 무게가 주어지면, 그 추를 양팔 저울에 적절히 올려서 구슬 무게를 맞출 수 있는지를 체크하면 된다. 모든 경우의 수를 고려하는 것은 시간초과가 나서 불가능하기때문에, dp를 이용한다.

문제 풀이

이 문제의 핵심은 dp식을 어떻게 세우느냐에 있다. 나는 바로 생각을 못해서, 살짝살짝 풀이를 참고했다. (ㅎㅎ) 링크 dp식은 다음과 같이 세울 수 있다.

  • bool dp[i][w] : i번째까지 고려했을 때 w라는 무게를 만들 수 있는가?

이렇게 dp식을 세우고 나면, i번째까지 고려했을 때 그 다음은 어떻게 해야할지 알 수 있다. 즉, 내가 i번째까지 고려해서 w라는 무게가 만들어 졌다면, dp[i][w]는 true가 된다. 그리고 i+1번째까지 고려할 때의 경우까지 고려할 수 있다. 여기에는 세가지가 있다.

  1. i+1번째 추를 담지 않고 i+1번째까지 고려한다.
  2. i+1번째 추를 담으면서 i+1번째까지 고려한다.
  3. i+1번째 추를 구슬이랑 같이 담으면서 i+1번째까지 고려한다. 이것을 이용해서 점화식을 세우면 된다. 즉,
1
2
3
4
5
6
7
8
9
10
11
12
void f(int i, int w){
    if(i>cn) return;
    if(w>40000) return;
    if(dp[i][w]) return;

    dp[i][w]=true;

    f(i+1, w+chu[i]);
    f(i+1, w);
    if (w-chu[i]>=0) f(i+1, w-chu[i]);
    else f(i+1, chu[i]-w);
}

가 된다. 여기서 중요한 점은 break되는 조건을 걸어주는 것인데, 이걸 걸어주지 않으면 f가 끝나지 않고 계속 돌게 된다. 즉, i번째까지 고려하는 이 i가 추 개수를 넘어설 때 break해주고, 총 무게가 40000이 넘어갈 때(조건에 있다) break를 걸어주고, 이미 true가 된 dp가 들어오면 break를 걸어준다. 이렇게 하면 양팔저울 문제를 풀 수 있다. 아래는 코드이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>

int cn;
int chu[31];
int bn;
int b[8];

bool dp[31][50000]={false, }; // dp[i][j] : i번째까지 담아서 j무게를 만들 수 있는가?

void f(int i, int w){
    if(i>cn) return;
    if(w>40000) return;
    if(dp[i][w]) return;

    dp[i][w]=true;

    f(i+1, w+chu[i]);
    f(i+1, w);
    if (w-chu[i]>=0) f(i+1, w-chu[i]);
    else f(i+1, chu[i]-w);
}

int main(){
    scanf("%d", &cn);
    for(int i=0;i<cn;i++) scanf("%d", &chu[i]);
    int bn;
    scanf("%d", &bn);
    for(int i=0;i<bn;i++) scanf("%d", &b[i]);

    f(0,0);

    for(int i=0;i<bn;i++){
        if(b[i]>15000) printf("%s ", "N"); // 여기서도 물어보는 무게가 30*500g이상이면 당연히안되므로 dp를 흝을이유도 없다
        else if(dp[cn][b[i]]) printf("%s ", "Y");
        else printf("%s ", "N");
    }
    printf("\n");
    
}