기타리스트 - 백준 1495 (Java)

 

 

 

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

처음 풀이

문제 읽고 처음 생각난 풀이는 DFS를 이용한 풀이었다.

곡이 진행되고 다음 곡이 진행되기 전에 볼륨을 조절하고, 볼륨이 범위 안에 있다면, 새로운 볼륨으로 다음 곡을 진행하고, 또 그 다음 곡이 진행되기 전에 볼륨을 조절하고.... 

중단 조건은 다음에 진행할 곡의 index가 전체 곡 개수와 같을 때이다. 즉 마지막 곡을 연주하고 나서 볼륨을 max값과 비교해 최대값으로 갱신한다.

위 과정을 코드로 나타내면 다음과 같다.

 

public static void dfs(int now, int index, int total, int limit) {
    if (index==total) {
        max = Math.max(max, now);
        return;
    }

    if ((now+vArr[index])<=limit) {
        dfs(now+vArr[index], index+1, total, limit);
    }
    if ((now-vArr[index])>=0) {
        dfs(now-vArr[index], index+1, total, limit);
    }
}

 

 

혹시나 해서 BFS로도 진행했다.

여기서 중요한 것은 볼륨 탐색하는 과정을 곡마다 그룹지어야 한다. 그러기 위해 한 곡에 대해 가능한 볼륨인지 검사할 볼륨 수를 cnt가 되게끔 하고 볼륨을 하나 검사할 때마다 (즉, queue에서 poll할 때마다) cnt를 하나씩 줄여 0이 될때까지 진행한다. 다음 곡에 대해 탐색할 볼륨은 queue에 추가할 때 tempCnt를 1씩 늘리고, 현재 곡에 대한 볼륨 탐색이 끝나면 다음 곡에 대해 진행하기 전에 tempCnt를 cnt에 대입해준다.

이를 코드로 나타내면 다음과 같다.

 

public static int bfs(int start, int total, int limit) {
    Queue<Integer> queue = new LinkedList<>();

    int index = 0;

    queue.add(start);

    int cnt = 1;

    int tempCnt = 0;

    while (!queue.isEmpty() && index!=total) {
        while (cnt--!=0) {
            int now = queue.poll();

            if (now+vArr[index]<=limit) {
                queue.add(now+vArr[index]);
                tempCnt++;
            }
            if ((now-vArr[index])>=0) {
                queue.add(now-vArr[index]);
                tempCnt++;
            }
        }//while end
        
        index++;
        cnt = tempCnt;
        tempCnt = 0;
    }//while end

    int max = -1;

    while (!queue.isEmpty()) {
        int temp = queue.poll();
        max = Math.max(max, temp);
    }//while end

    return max;
}

 

 

문제의 조건을 보니 곡의 수가 최대 50까지라서 최악의 경우 2^50회 볼륨에 대해 검사를 해야한다. 당연히 시간, 공간이 초과할 수 밖에 없는 상황이었다. 문제 풀기 전에 조건을 보고 대략적인 O(N)을 고민하지 않은 내 잘못이었다.

 

다른 풀이

혹시 dp로 풀리려나 고민하고 있엇는데 풀이를 찾아보니 dp로 대부분 풀었다.

​

dp[N][M+1]을 만든다. 의미는 a+1번째 곡이 볼륨 b로 연주가 가능하다면 dp[a][b]가 1이고, 불가능하다면 0의 값을 갖도록 한다.

마지막으로는 dp[N-1]을 뒤부터 탐색하면서 제일 먼저 값이 1이 되는 볼륨을 출력하면 된다. 만일 dp[N-1]에서 값이 1이 된느 볼륨이 없다면 -1을 출력한다.

static int[] vArr;
static int[][] dp;
    
public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

    int N = Integer.parseInt(st.nextToken());
    int S = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    vArr = new int[N];

    st = new StringTokenizer(bf.readLine(), " ");

    for (int i = 0; i < N; i++) {
        vArr[i] = Integer.parseInt(st.nextToken());
    }//for end

    dp = new int[N][M+1];

    //첫 번째 곡
    if (S + vArr[0] <= M) dp[0][S + vArr[0]] = 1;
    if (S - vArr[0] >= 0) dp[0][S - vArr[0]] = 1;

    //두 번째 곡부터 연주 가능한 볼륨 탐색
    for (int i = 1; i < N; i++) {
        calculate(i, M);
    }//for end

    int max = -1;

	//마지막 곡을 연주할 수 있는 볼륨 중 최댓값으로 갱신!
    //가능한 볼륨값이 없다면 -1 그대로
    for (int i = M; i >= 0; i--) {
        if (dp[N-1][i] == 1) {
            max = i;
            break;
        }
    }//for end

    System.out.println(max);

}

//index번째 곡 연주 가능한 볼륨 표시
public static void calculate(int index, int M) {
    for (int i = 0; i <= M; i++) {
    	//직전 곡 연주 가능한 볼륨에서 현재 곡 연주 직전 변경가능한 볼륨 +, - 해준 새 볼륨을 검사
        if (dp[index-1][i] == 1) {
            if (i + vArr[index] <= M) dp[index][i + vArr[index]] = 1;
            if (i - vArr[index] >= 0) dp[index][i - vArr[index]] = 1;
        }
    }//for end
}