[Baekjoon] 1495_기타리스트

Silver I

문제(출처: https://www.acmicpc.net/problem/1495)

---

< 기타리스트 >

 

문제 풀이 

 

처음에는 queue를 사용해서 가능한 모든 볼륨을 add와 pop을 통해 구했다. 이렇게 구현할 경우 메모리 초과가 발생해서 어떻게 고쳐야 할지 몰랐다. 

 

찾아본 결과 0 이상 M이하의 값만 가능하므로 배열을 m+1만큼 선언한 후에 배열[볼륨] = 인덱스로 값을 구하여 메모리 초과가 발생하지 않는다.

 

예를 들어

1 5 10

5 

이라면 temp [5]=1로 초기화한 후에 0번째 곡을 연주하기 위해 볼륨을 바꾼다고 하자.

temp [10]=2, temp [0]=2가 된다. 0 이상 M이하인 배열을 전체 탐색하여 배열 값이 2인 인덱스 중에 최댓값을 출력한다.

 

 my solution (Java)

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

public class _1495_ { // 기타리스트

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(bf.readLine());
		int arr[] = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int temp[] = new int[m + 1];
		temp[s] = 1;
		boolean flag = false;

		for (int i = 0; i < n; i++) {
			flag = false;
			ArrayList<Integer> list = new ArrayList<>();
			for (int j = 0; j < m + 1; j++) {
				if (temp[j] == i + 1) {
					if (j + arr[i] <= m) {
						list.add(j + arr[i]);
						flag = true;
					}
					if (j - arr[i] >= 0) {
						list.add(j - arr[i]);
						flag = true;
					}
				}
			}
			for (int j : list) {
				temp[j] = i + 2;
			}
			if (!flag) {
				break;
			}
		}

		int result = -1;
		for (int i = 0; i < m + 1; i++) {
			if (temp[i] == n + 1) {
				result = Math.max(result, i);
			}
		}
		System.out.println(result);
	}
}

변수)
n, s, m : 곡의 개수, 시작 볼륨, 볼륨 최댓값
arr : 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이
temp : 볼륨 조절 배열
flag : 마지막 곡을 연주할 수 있는지 판단하는 boolean 
list : 중간에 배열 값을 변경하지 않게 하기 위해 저장하는 ArrayList
result : 마지막 곡의 볼륨 중 최댓값

 

temp [s]=1로 저장한다. 볼륨 s가 시작 볼륨이므로 1을 저장한다.

arr 배열을 전체 순환하며 temp 배열도 같이 순환한다. temp 배열의 값이 i+1 값이라면 다음 곡을 연주하기 위해 볼륨 조절을 해야 하므로 P+arr [i], P-arr [i]을 구한 후 0 이상 M이하 값이라면 i+2 값으로 저장한다.

 

최종 temp 배열을 순환하며 값이 n+1인 값 중에 최댓값을 구해 출력한다.

---

---