[BOJ] 1495 기타리스트 - JAVA

1. 문제

1495번: 기타리스트

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

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

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

---

2. 풀이

입력

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());//곡 개수
int S = Integer.parseInt(st.nextToken());//시작 볼륨
int M = Integer.parseInt(st.nextToken());//볼륨 최댓값

int[] V = new int[N];
st = new StringTokenizer(in.readLine());
for(int i=0;i<N;i++) V[i] = Integer.parseInt(st.nextToken());

 

탐색

현재 곡을 i라고 할 때, i-1번째 곡을 연주할 수 있는 볼륨 경우의 수를 prev에 저장한다.

i번째 곡을 연주할 수 있는 볼륨 경우의 수는 now에 저장하고 탐색이 끝난 후 prev를 교체한다.

prev, now는 모두 M+1칸이다. (최대 볼륨 칸 수)

M+1개의 칸을 탐색하면서 prev[j]가 true라면(=이전 곡을 연주할 수 있는 볼륨이라면) 범위에 벗어나지 않는 선에서 V[i]를 더하고 뺀 값에 true를 저장한다.

boolean[] prev = new boolean[M+1];
prev[S] = true;

boolean[] now;
for(int i=0;i<N;i++){
   now = new boolean[M+1];
   for(int j=0;j<=M;j++){
      if(!prev[j]) continue;
      if(j+V[i] <= M) now[j+V[i]] = true;
      if(j-V[i] >= 0) now[j-V[i]] = true;
   }
   prev = now;
}

 

출력

탐색이 끝난 뒤에는 prev와 now가 동일하다. 아무거나 선택해서 true가 저장되어 있는 칸 수를 세고 출력한다.

int volume = -1;
for(int i=M;i>=0;i--){
   if(prev[i]){
      volume = i;
      break;
   }
}

System.out.println(volume);

 

전체 코드

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

public class BOJ_1495_기타리스트 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());//곡 개수
      int S = Integer.parseInt(st.nextToken());//시작 볼륨
      int M = Integer.parseInt(st.nextToken());//볼륨 최댓값

      int[] V = new int[N];
      st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) V[i] = Integer.parseInt(st.nextToken());

      boolean[] prev = new boolean[M+1];
      prev[S] = true;

      boolean[] now;
      for(int i=0;i<N;i++){
         now = new boolean[M+1];
         for(int j=0;j<=M;j++){
            if(!prev[j]) continue;
            if(j+V[i] <= M) now[j+V[i]] = true;
            if(j-V[i] >= 0) now[j-V[i]] = true;
         }
         prev = now;
      }

      int volume = -1;
      for(int i=M;i>=0;i--){
         if(prev[i]){
            volume = i;
            break;
         }
      }

      System.out.println(volume);

   }
}

---

3. 결과

prev, now를 사용하지 않고 이차원 배열을 사용하는 방식을 써봤는데, 별로 큰 차이는 없었다.