[Silver I] 기타리스트 - 1495
성능 요약
메모리: 16420 KB, 시간: 128 ms
분류
다이나믹 프로그래밍
제출 일자
2025년 4월 7일 00:28:50
문제 설명
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을 출력한다.
# [Silver I] 기타리스트 - 1495성능 요약
메모리: 16420 KB, 시간: 128 ms
분류
다이나믹 프로그래밍
제출 일자
2025년 4월 7일 00:28:50
문제 설명
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을 출력한다.
구하고자 하는 것
마지막 곡까지 연주했을 때의 볼륨의 최대값을 구해야 한다.
단, 모든 단계에서 볼륨은 M보다 커질 수 없으며 0보다 작아질 수 없다.
풀이 설계하기
기업 코테에서 흔히 저지르는 실수이고 부끄럽게도 나도 최근에 저지른 실수 중 하나가 무조건 완전 탐색을 사용하는 것이다.
N이 50이라 얼핏 보기에는 작아 보이지만, 최대 2의 50승까지 가지 수가 치솟기 때문에 완전 탐색으로는 어림없다.
그렇다고 해서, 각 단계에서 무조건 최대 볼륨을 취하는 것도 최적해가 될 수 없다.
i번째 곡은 i-1번까지 곡의 볼륨보다 반드시 V[i]만큼 크거나 작은 볼륨이기 때문이다.
점화식 설계
내가 사고한 단계는 다음과 같았다.
흔히 점화식으로 계산되는 배열을 dp라는 이름의 변수로 정의하고 사용하는데, 이 dp를 어떤 형태로 정의하느냐가 중요하다.
- 각 곡에서 최대 볼륨을 취하는 것은 다음 단계의 볼륨만큼 크거나/작기에 최적해가 될 수 없음
- 그래서 각 곡의 볼륨마다 나타날 수 있는 모든 상태를 저장한 배열을 dp[i]라고 하기로 했는데, 단순 한 값을 최적해로 취하는 방법은 없음
따라서 이차원 배열, 혹은 컬렉션 배열을 사용하기로 함 - 인접 행렬로 나타내면 dp[i][j]는 i번 곡에서 볼륨 j가 존재한다는 뜻이고, ArrayList나 Set의 배열로 나타내면 인접 리스트가 됨
- dp[i-1]의 모든 상태에 +V[i], -V[i]를 취해서 0보다 크고 M보다 작은 값만을 저장함
- 이를 반복해서 마지막 dp[N]의 최대값을 구하면 되고, 만약 dp[i]의 최대값이 0이거나 컬렉션이 비었으면(아니면 반복 중에 체크해도 무방) 볼륨을 맞출 수 없으므로 -1을 출력
만약 리스트나 집합을 사용한다면(중복이 크지는 않을 것 같으나 거슬려셔 Set으로 사용함)
dp[i-1]의 모든 수를 꺼내고, 각 수를 number라고 한다면
- if(number + V[i] <= M) dp[i].add(number + V[i]);
- if(0 <= number - V[i]) dp[i].add(number - V[i]);
으로 나타낼 수 있다.(number가 0 이상 M 이하임이 보장되므로 number+V[i]는 0과 비교할 필요 없고, number-V[i]가 M과 비교될 필요도 없다)
따라서 위와 같이 최종 점화식이 도출되었으니 시간 복잡도를 검증해 보자.
시간 복잡도
boolean으로 쓰는 경우를 보자.
볼륨의 범위는 0 이상, M 이하이므로 0 ~ 1000까지의 범위를 갖는다.
이전 배열에서 최대 M 2(더하고 빼고) 만큼의 연산이 발생하고, 이것이 N번 반복된다.
dp[N][M] 배열에서는 O(N (M + 1))의 연산이 발생한다.
따라서 50 * 1001이므로 시간 내 충분히 해결이 가능하다.
그리고 set으로 문제를 푼다면 최악의 경우는 위와 같지만, 대부분 경우에서 어느 정도 연산 횟수를 줄이는 효과가 꽤 있으리라 짐작한다
정답 코드
import java.io.*;
import java.util.*;
@SuppressWarnings("unchecked")
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int S = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] volumes = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
volumes[i] = Integer.parseInt(st.nextToken());
}
HashSet<Integer>[] dp = new HashSet[N + 1];
for (int i = 0; i <= N; i++) {
dp[i] = new HashSet<Integer>();
}
dp[0].add(S);
for (int i = 1; i <= N; i++) {
if(dp[i - 1].isEmpty()) break;
for(int vol: dp[i-1]){
int upVol = vol + volumes[i];
int downVol = vol - volumes[i];
if(upVol <= M) dp[i].add(upVol);
if(0 <= downVol) dp[i].add(downVol);
}
}
int answer = -1;
if(dp[N].isEmpty()) System.out.println(answer);
else{
for(int vol: dp[N]){
answer = Math.max(vol, answer);
}
System.out.println(answer);
}
}
}컬렉션을 배열로 선언해서 컴파일러의 오류가 나서 어노테이션을 추가했다.
그런데 이것을 고치려니 너무.. 귀찮아서 이것도 외워둬야 하나? 싶다
