(c++) 동적계획법 BOJ 2629번: 양팔저울

https://www.acmicpc.net/problem/2629

2629번: 양팔저울

 

 

 

문제 개요

 

 

배낭 문제와 동일한 냅색(KnapSack) 문제 중 하나이다.

 

배낭 문제는 물건을 넣기, 물건을 안 넣기 두 개로 나누었는데

 

양팔 저울 문제는 세 가지로 나눈다.

추를 안 올리기

왼쪽에 추 올리기

오른쪽에 추 올리기

 

왼쪽 저울에 비교할 추가 올라간다고 생각하면

왼쪽에 추를 올릴 경우 비교할 추 무게를 더해주면 되고

오른쪽에 추를 올릴 경우는 비교할 추 무게를 빼주면 된다.

 

// 안 넣기
check(weight, chu+1);
// 오른쪽 넣기
check(abs(weight - ch_array[chu]), chu+1);
// 왼쪽 넣기
check(weight + ch_array[chu], chu+1);

 

abs 함수는 절댓값으로 바꾸어 음수가 나오지 않도록 하는 부분이다.

 

 

코드

 

 

bool 부울식을 이용해서 추의 개수가 넘어가거나 해당 위치가 false이면 넘어가는 식이다.

 

#include <bits/stdc++.h>

using namespace std;
// ch = 추의 개수
int ch;
int ch_array[31];
bool cache[40500][31];

void check(int weight, int chu) {
    if (chu > ch || cache[weight][chu]) return;
    cache[weight][chu] = true;
    // 안 넣기
    check(weight, chu+1);
    // 오른쪽 넣기
    check(abs(weight - ch_array[chu]), chu+1);
    // 왼쪽 넣기
    check(weight + ch_array[chu], chu+1);
}

int main(void) {
    cin >> ch;
    for (int i = 0; i < ch; i++) {
        cin >> ch_array[i];
    }
    check(0, 0);
    int cicle;
    cin >> cicle;
    for (int i = 0; i < cicle; i++) {
        int check_ci;
        cin >> check_ci;
        if (cache[check_ci][ch]) cout << "Y" << " ";
        else cout << "N" << " "; 
    }
}