[BOJ] 2629 : 양팔저울

문제 링크

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

2629번: 양팔저울

풀이

백트래킹을 공부하다가 만난 문제다. 저울을 기준으로 생각했을 때 i번째 추를 처리하는 방법은 3가지가 있다.

1. 왼쪽에 놓는다

2. 오른쪽에 놓는다

3. 놓지 않는다

맨 처음 떠오른 아이디어가 이것이었으므로 이것을 기반으로 코드를 작성했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAX_N = 40000 + 5;
int is_ok[MAX_N];
int N, T;
vector<int> weight;
 
void backtracking(int depth, int Left, int Right) {
    if (is_ok[abs(Left - Right)])
        return;
    is_ok[abs(Left - Right)] = 1;
    if (depth == N) {
        return;
    }
    backtracking(depth + 1, Left + weight[depth], Right); //추를 왼쪽에 올리거나
    backtracking(depth + 1, Left, Right + weight[depth]); //추를 오른쪽에 올리거나
    backtracking(depth + 1, Left, Right); //추를 안올리거나
}
int main(void)
 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    int num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        weight.push_back(num);
    }
    cin >> T;
    backtracking(0, 0, 0);
    while (T--) {
        cin >> num;
        if (is_ok[num])
            cout << "Y";
        else cout << "N";
        cout << " ";
    }
    return 0;
}
 
 

이렇게 세 갈래의 백트래킹을 진행한 결과. 시간초과를 맞이했다. 생각해보면 이 코드의 시간복잡도는

3의 N제곱. N이 최대 30이니까 최악의 경우 3의 30제곱. 시간제한은 1초밖에 안되는데 3의30제곱은 10억을

훌쩍 뛰어넘는 숫자다. 시간을 줄이기 위해 한참을 고민했다. 3의 10제곱은 5만 남짓하니까 30이면 10개씩 3개로 나눠서 계산하면 되지않을까? 했는데 코드로 구현하기가 불가능한건지 어려웠다. 결국 고민끝에 다른분의 코드를 참고하기로 했다. 

참고한 코드

https://cocoon1787.tistory.com/360

[C/C++] 백준 2629번 - 양팔저울 (DP풀이)

이 분의 코드를 보면 매커니즘은 나와 비슷하다. 차이가 있다면

if (i > n || dp[i][w]) return;

이 부분만 달랐다. 나는 is_ok라는 1차원 배열에 그 구슬의 무게가 측정 가능한지 여부를 저장하고 있었고 저 분은 2차원 배열을 만들어 i개 까지 검사했을때 w의 무게 구슬을 측정 가능한지 여부를 저장했다.

그리고 dp[i][w]가 가능하다고 판별났으면 return해서 중복을 방지했다. 이 부분을 참고해서 내 코드를 수정했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAX_N = 40000 + 5;
bool is_ok[31][MAX_N];
int N, T;
vector<int> weight;
 
void backtracking(int depth, int Left, int Right) {
    if (is_ok[depth][abs(Left - Right)])
        return;
    is_ok[depth][abs(Left - Right)] = 1;
    if (depth == N)
        return;
    backtracking(depth + 1, Left + weight[depth], Right); //추를 왼쪽에 올리거나
    backtracking(depth + 1, Left, Right + weight[depth]); //추를 오른쪽에 올리거나
    backtracking(depth + 1, Left, Right); //추를 안올리거나
}
int main(void)
 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    int num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        weight.push_back(num);
    }
    cin >> T;
    backtracking(0, 0, 0);
    while (T--) {
        cin >> num;
        if (is_ok[N][num])
            cout << "Y";
        else cout << "N";
        cout << " ";
    }
    return 0;
}
 
 

그렇게 제출한 결과 시간초과를 피할 수 있었다. 냅색의 저장방식을 활용해서 시간복잡도를 낮춘 케이스였다.

저장하는 방법을 설정할 때 신중해야 한다는 것을 알게해 준 문제다.