[Algorithm]Baekjoon 2629번 :: 양팔저울

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

2629번: 양팔저울

 
int balanceWeightNum;
int balanceWeights[31] = { 0 };
int beadNum, beadWeight;
bool check[31][15001] = { false };
 
void DFS(int index, int sum)
{
    if (index > balanceWeightNum || check[index][sum]) return;
 
    check[index][sum] = true;
    ++index;
 
    DFS(index, sum + balanceWeights[index]); // 구슬반대편
    DFS(index, sum);
    DFS(index, abs(sum - balanceWeights[index])); // 구슬쪽
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> balanceWeightNum;
 
    for (int i = 1; i <= balanceWeightNum; ++i)
    {
        cin >> balanceWeights[i];
    }
 
    DFS(0, 0);
 
    cin >> beadNum;
 
    for (int i = 0; i < beadNum; ++i)
    {
        cin >> beadWeight;
 
        if (beadWeight > 15000 || check[balanceWeightNum][beadWeight] == false)
        {
            cout << 'N' << ' ';
        }
        else
        {
            cout << 'Y' << ' ';
        }
    }
}

 

꽤 어려웠던 문제였다.

풀이를 보고나서야 '이런식으로 해석해서 푸는구나..'라고 이해했다. 풀기이전의 내 상태에서는 해당영역까지 생각을 확장하지 못했을것이다.

 

잴 수 있는 무게를 구하는것을, 추를 세가지방법으로 놓는것으로 표현했다.

 

1. '구슬이 있는 곳'에 놓는다.

         -> 만약 구슬반대편에 5g가 있고, 구슬이 있는곳에 1g가 있을경우 구슬은 4g이며 해당무게를 체크할 수 있다.

             즉, 구슬이 있는곳에 놓는다면 '현재 구슬반대편에 쌓인 무게 - 구슬에있는곳에 놓은 추의 무게' 만큼을 체크할 수 있다.

 

2. 그냥 아예 안놓는다.

       -> 이번 차례의 추를 놓는것을 포기하고 다음무게의 추로 넘어간다.

 

3. '구슬이 있는 곳 반대편'에 놓는다.

       -> 구슬반대편에 놓아서 누적값을 증가시킨다.

 

 

풀이를 글로만 본다음 check를 1차원으로 했었는데 통과가 되지 않아 다시 보고 디버깅해보니, 현재 차례에 누적하는것을 그냥 넘겼을 때 (15번 째), 1차원이면 넘긴다음 DFS에서 check가 true가 되어있기 때문에(이전단계때 true로 했었으니까) 탐색이 더이상 되지않고 멈춰버렸었기 때문에 통과가 되지 않았었다.

 

참고로 추는 최대 500g짜리가 30개까지만 쌓이기때문에, dp값 체크는 15000까지만 하면된다.

그러나 체크하고자하는 구슬의 무게는 최대 40000이니까 출력할 때 적절히 예외처리를 해줘야 한다.