boj1495 기타리스트

링크

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보다 작거나 같다.

출력

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

나의 풀이

• greedy 하게 풀면 N이 50개 이기 때문에 시간초과가 난다.
• 참고 풀이 : https://velog.io/@yanghl98/백준-1495-기타리스트-JAVA자바
• 방법을 모르겠어서 답을 봤다. 전형적인 dp풀이 방법인데도 막상 풀이를 할때는 생각을 못했다.
• M길이만큼의 dp를 만들고, 인덱스마다 연산했을때 나오는 값을 P라고 했을때, dp[P]에 해당 인덱스값을 넣어 주었다.
  • 이때, dp 배열에 인덱스가 0 인 초기값도 넣어주어야 하기 때문에, 처음에 -1로 모두 세팅하고, Arrays.fill(dp,-1) 이후에, dp[0]=S 를 해주면 dp세팅이 끝난다.
  • 그리고 나서는 1~N만큼 for문을 돌면서 인덱스마다 나올 수 있는 수들을 체크해주고, 마지막 인덱스에서 가장 큰값을 answer에 담으면 된다. 이때, answer의 기본값을 -1로 해주면, 담을게 없으면 기존 answer가 출력되기 때문에, answer가 나오지 않는 경우를 따로 체크하지 않아도 된다.
• 시간을 4ms 줄인 코드 for문을 다 돌았는데도 queue가 비어있으면, 불가능한 경우이므로, 해당 함수를 그냥 나가게 처리했다.

  outer:
  for (int i = 1; i <= N; i++) {
      for (int j = 0; j <= M; j++) {
          if(dp[j]==i-1){
              if(isRange(j+V[i])) {
                  queue.add(V[i]+j);
              }if(isRange(j-V[i])){
                  queue.add(j-V[i]);
              }
          }
      }
      if(queue.isEmpty()) break outer;
  ...
  }

• 핵심 코드

  private static void getMaxV(int idx,int val){
          Queue<Integer> queue = new LinkedList<>();
          outer:
          for (int i = 1; i <= N; i++) {
              for (int j = 0; j <= M; j++) {
                  if(dp[j]==i-1){
                      if(isRange(j+V[i])) {
                          queue.add(V[i]+j);
                      }if(isRange(j-V[i])){
                          queue.add(j-V[i]);
                      }
                  }
              }
              if(queue.isEmpty()) break outer;
  
              while(!queue.isEmpty()){
                  int p = queue.poll();
                  dp[p] = i;
                  if(i==N){
                      if(answer<p) answer = p;
                  }
              }
          }
  
      }

• 전체 코드

  package Baekjoon.java.silver;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.LinkedList;
  import java.util.Queue;
  import java.util.StringTokenizer;
  
  public class boj1495 {
      static int N,M,answer,V[],dp[];
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
  
          N = Integer.parseInt(st.nextToken());
          int S = Integer.parseInt(st.nextToken());
          M = Integer.parseInt(st.nextToken());
          answer = -1;
  
          V = new int[N+1];
          dp = new int[M+1];
          Arrays.fill(dp,-1);
          dp[S]=0;
          st = new StringTokenizer(br.readLine());
          for (int i = 1; i <= N; i++) {
              V[i] = Integer.parseInt(st.nextToken());
          }
  
          getMaxV(0,S);
  
          System.out.println(answer);
  
      }
      private static boolean isRange(int n){
          return n>=0&&n<=M;
      }
  
      private static void getMaxV(int idx,int val){
          Queue<Integer> queue = new LinkedList<>();
          outer:
          for (int i = 1; i <= N; i++) {
              for (int j = 0; j <= M; j++) {
                  if(dp[j]==i-1){
                      if(isRange(j+V[i])) {
                          queue.add(V[i]+j);
                      }if(isRange(j-V[i])){
                          queue.add(j-V[i]);
                      }
                  }
              }
              if(queue.isEmpty()) break outer;
  
              while(!queue.isEmpty()){
                  int p = queue.poll();
                  dp[p] = i;
                  if(i==N){
                      if(answer<p) answer = p;
                  }
              }
          }
  
      }
  }

결과