[백준] 1495 : 기타리스트 (JAVA/자바)

문제

BOJ 1495 : 기타리스트 - https://www.acmicpc.net/problem/1495

풀이

N개의 곡 연주하는데, 볼륨의 선택지는 2가지이다. 기존 볼륨+V[i]와 기존볼륨-V[i]. 처음엔 재귀 호출로 풀이하려고 생각했는데 N이 최대 100이기 때문에 O(2^100)이 되어서 시간초과가 날 게 뻔했다.. DP로 풀이해야하는 문제.

'맨 마지막 곡의 최댓값을 구해야 하니까, 각각의 곡이 최댓값을 가지면 되지 않을까?' 하고 생각했지만 볼륨의 범위가 0<=P<=M 로 제한되어있기 때문에 무조건 크게 할 수가 없다.

범위 0~M을 가지는 volume 배열을 만들었다. volume[v] = i는 i번째 연주에서 볼륨 v으로 연주할 수 있다는 걸 의미한다. 즉, 볼륨 v로 연주할 수 있는 곡 번호는 i이다. 최종적으로 volume[x] = N 인 x중에서 가장 큰 값이 결과값이 된다!

예를 들어, volume[2]가 2이고 volume[6]이 2이면, 2번째 곡은 볼륨 2 혹은 6로 연주할 수 있다는 의미가 된다. 3번째 곡은 2번째 곡을 연주할 수 있는 2 혹은 6에서 V[3]을 더하거나 빼는 경우가 가능하다. V[3]이 4라면, 2-4=-2(X) / 2+4=6(O) / 6-4=2(O) / 6+4=10(O) 와 같은 식이다.

가능한 볼륨값은 리스트로 저장해놓은 뒤, 한번에 volume 배열 값을 바꾸어주었다. 리스트에 저장하지 않고 바로 변경해버리면 이전 볼륨 내역이 덮어쓰기 되어 값이 틀리게 나올 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;


public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int N = Integer.parseInt(inputs[0]);
        int S = Integer.parseInt(inputs[1]);
        int M = Integer.parseInt(inputs[2]);

        int[] diff = new int[N+1];
        inputs = br.readLine().split(" ");
        for (int i = 1; i <= N; i++) {
            diff[i] = Integer.parseInt(inputs[i-1]);
        }

        int[] volume = new int[M + 1];
        for(int i=0; i<=M; i++){ // initialize : 0은 S의 초기값이기 때문에 -1로 초기화 시킨 후 진행
            volume[i] = -1;
        }
        volume[S] = 0;

        ArrayList<Integer> list = new ArrayList<>();

        for(int i=1; i<=N; i++){ // 연주 idx
            list.clear();
            for(int j=0; j<=M; j++) { // 볼륨 idx
                if(volume[j] == i-1) { // 이전 연주(i-1)가 j 볼륨으로 연주가 가능했으면
                    if (0 <= j - diff[i] && j - diff[i] <= M) { // 0~M 범위에 속한다면
                        list.add(j - diff[i]);
                    }
                    if (0 <= j + diff[i] && j + diff[i] <= M) {
                        list.add(j + diff[i]);
                    }
                }
            }
            for (int v : list) {
                volume[v] = i;
            }
        }

        for(int i=M; i>=0; i--){
            if(volume[i] == N){
                System.out.println(i);
                return;
            }
        }
        System.out.println(-1);
    }
}

정리

✔ 알고리즘 분류 - 다이나믹 프로그래밍
✔ 난이도 - ⚪ Silver 1

🤦‍♀️ 오늘의 메모

• DP문제,,, 좀 더 열심히 풀어야겠다.

• 이중 배열을 이용해서 풀이하는 방법도 있는 것 같은데, 풀어보고 정리해보도록 하겠다!

참고 사이트

https://lotuslee.tistory.com/131