[백준] 1495: 기타리스트 (DP) - JAVA

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

 

 

# 문제

Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

 

# 예제

입력 :  첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

3 5 10
5 3 7

 

 

출력 : 첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.

10

 

 

# 필요개념

여러 풀이를 시도했으나 결과가 다음과 같았다.

 

ㅎㅡㅎ

dfs를 이용했을 때에는 시간초과가 발생했고, 리스트배열을 쓸 땐 메모리초과가 발생했다. 어찌보면 당연하긴 하다.. 

dfs는 재귀호출을 하기 때문에 시간복잡도가 2^50 (N의 최대가 50이기 때문)이 나오고, 리스트배열을 쓰면 2^50크기의 리스트를 넣은 배열을 사용하므로 메모리초과가 난다. 

 

리스트배열을 쓴 이유는 배열의 크기를 지정할 수 없기 때문이었는데, 조금만 바꾸어 생각하면 크기를 지정할 수 있다.

이 문제에서 볼륨의 상한선을 M으로 지정해두었기 때문에, 배열의 크기를 지정할 수 있었다.

 

볼륨 크기를 값이 아닌 인덱스로 활용하기로 하고, 이차원 배열을 생성했다. 이 이차원 배열에 값이 있으면 true, 없으면 false를 넣는다. dp를 풀 땐 항상 배열의 크기에 관한 고민을 깊게 해보자..

 

# Code

import java.util.*;
import java.io.*;

public class Main {
    static int max;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());
        max = Integer.parseInt(st.nextToken());

        boolean[][] dp = new boolean[N + 1][max + 1];
        dp[0][start] = true;

        st = new StringTokenizer(br.readLine());

        for (int i = 1 ; i <= N ; i++) {
            int input = Integer.parseInt(st.nextToken());
            for (int j = 0 ; j <= max ; j++) {
                if (dp[i - 1][j]) {
                    int p = j + input;
                    int m = j - input;

                    if (check(p)) dp[i][p] = true;
                    if (check(m)) dp[i][m] = true;
                }
            }
        }

        int ans = -1;
        for (int i = max ; i >= 0 ; i--) {
            if (dp[N][i]) {
                ans = i;
                break;
            }
        }
        System.out.println(ans);
    }

    private static boolean check(int num) {
        return num <= max && num >= 0;
    }
}

 

# 결과