[JAVA/백준/1495] 기타리스트 / DP

1495번: 기타리스트

 

풀이 과정

기타의 볼륨을 조절하여 연주할 수 있는 곡 중에서, 마지막 곡을 연주할 때 볼륨의 최댓값을 구하는 문제다

이 문제를 해결하기 위해서는 가능한 모든 볼륨을 조합해봐야 하며 시간과 메모리를 적게 소모하기 위해서는 동적 계획법(Dynamic Programming)을 사용할 수 있다

 

 

우선 입력값을 받아와서, 가능한 볼륨을 저장하는 배열인 dp를 초기화한다

그리고 첫번째 곡을 연주할 때, 현재 볼륨(S)을 인덱스로 가지는 dp배열의 값을 true로 설정한다

그리고 이후에는 두번째 곡부터 N번째 곡까지 반복해서 연주한다

 

1. 이 때, 각 곡마다 가능한 모든 볼륨을 조합해봐야 하므로, 이전 곡에서 가능했던 볼륨들을 모두 가져온 뒤, 리스트에 넣음

2. 현재 곡에서 가능한 볼륨을 더해주거나 빼주어 새로운 가능한 볼륨들을 만들어주고 다시 dp 배열의 해당 값을 true로 하며 리스트도 초기화

3. 이렇게 만들어진 가능한 볼륨들을 dp 배열에 true 값 중에서 가장 큰 인덱스를 찾아 그 값을 출력

 

 

결과 코드

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

public class Main {

  private static int N, S, M;
  private static int max; // 최대 볼륨
  private static int[] volumes; // 볼륨 조절기에서 각각 볼륨을 올리거나 내리는 값
  private static boolean[] dp; // dp[i]는 i번째 시도에서 볼륨값들

  public static void main(String[] args) throws IOException {
    Main.start();
  }

  private static void start() throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    // 입력 받기
    N = Integer.parseInt(st.nextToken()); // 시도 횟수
    S = Integer.parseInt(st.nextToken()); // 초기 볼륨
    M = Integer.parseInt(st.nextToken()); // 볼륨 조절기로 올릴 수 있는 최대 볼륨
    max = -1;

    dp = new boolean[M + 1];
    dp[S] = true; // 초기 볼륨 가능

    volumes = new int[N];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
      volumes[i] = Integer.parseInt(st.nextToken());
    }

    // 볼륨을 조절하는 과정을 반복문으로 구현
    ArrayList<Integer> al = new ArrayList<>();
    for (int i = 0; i < N; i++) {
      al.clear(); // 이전 시도에서 가능한 최대 볼륨 초기화

      // 이전 시도에서 가능한 최대 볼륨들을 기반으로 다음 시도에서 가능한 최대 볼륨 계산
      for (int j = 0; j <= M; j++) {
        if (dp[j] == true) {
          dp[j] = false; // 이전 시도에서 가능한 최대 볼륨 사용

          // 볼륨을 올리는 경우
          if (j + volumes[i] <= M) {
            al.add(j + volumes[i]);
          }

          // 볼륨을 내리는 경우
          if (j - volumes[i] >= 0) {
            al.add(j - volumes[i]);
          }
        }
      }

      // 다음 시도에서 가능한 최대 볼륨들을 저장
      for (Integer integer : al) {
        dp[integer] = true;
      }
    }

    // 가능한 최대 볼륨 중 가장 큰 값 찾기
    for (int i = M; i >= 0; i--) {
      if (dp[i] == true) {
        max = i;
        break;
      }
    }

    System.out.println(max);
  }
}