[BOJ] 1495. 기타리스트 (dp)

Silver I

https://www.acmicpc.net/problem/1495

1495번: 기타리스트

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

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

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

 

input:

• 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M)
• 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

output:

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

 

---

Idea :

• DFS vs DP
  • 처음 문제를 접했을 때, DFS 문제라고 생각했었으나 N, M값이 커서 시간초과가 나지 않을까 생각
  • 시간 초과로 DFS가 아니라면 DP로 풀어야 된다고 생각을 했지만, 어떤 식으로 접근해야 할 지 감이 안잡힘
  • 결국 DFS로 구현... 시간 초과가 나왔다..ㅎ 
• DP ( 다른 코드 참고 )
  1.  DFS 응용
     • DFS 코드에 메모리제이션 부분만 추가해도 시간 내에 해결 가능 
     • 재귀함수를 호출하기 전에 해당 노래를 연주하기 전(현재 노래의 볼륨을 바꾸기 전) 볼륨이 이전에 나온 적 있는지 확인하고, 처음일 경우에만 재귀함수 호출
     • 같은 계산을 여러번 하는 걸 방지할 수 있음
     • 이게 왜 DP인가.. → DP의 top down 방식, 이전 계산 결과를 저장해놨기 때문에 memorization 사용
  2. bottom up DP 
     • dp[i][v] = i 번째 노래에 대해 v 크기의 불륨으로 연주할 수 있는지 여부를 저장하고 있음
     • dp[i-1]를 순회하면서 dp[i-1][v] == true가 되는 v에 대해서
       현재 곡 i 번째 곡의 불륨을 계산, dp[i][cur_volume] true로 체크
     • 위 동작을 N번째 곡까지 반복, dp[N][v] == true 가 되는 v 중 가장 큰 값이 답이 됨
     • 예시 더보기 참고

예시 N=3, S=3, M=8, v_list = {3, 1, 5}

 

i \ v	0	1	2	3	4	5	6	7	8
S				O
1	O						O
2		O				O		O
3	O						O

dp[0][S] 인 dp[0][3]이 true이므로, dp[1][3 - 3] = dp[1][3 + 3] = true

dp[1][0] → dp[1][0 - 1], dp[1][0 + 1] 중 0 <= v <= M인 dp[1][1] = true

.... (N까지 반복)

dp[N] 중 true인 v는 {0, 6} 그 중 가장 큰 값인 6이 답이 됨

 

▶ answer = 6

 

Code  1: DFS 활용 / DP top-down   

#include <iostream>

using namespace std;

int N, S, M;
int v_list[50] = {};
bool dp[50][1001] = {};
int maxV = -1;

void dfs(int depth, int v) {
	if (depth == N) {
		if (v > maxV) maxV = v;
		return;
	}
	if (dp[depth][v]) return;
	dp[depth][v] = true;

	if (v + v_list[depth] <= M) 
		dfs(depth+1, v + v_list[depth]);
	if (v - v_list[depth] >= 0) 
		dfs(depth+1, v - v_list[depth]); 
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	cin >> N >> S >> M;
	for (int i=0; i<N; i++) cin >> v_list[i];

	dfs(0, S);
	cout << maxV << "\n";
}

 

Code 2: DP bottom-up

#include <iostream>

using namespace std;

int N, S, M;
int v_list[51] = {};
bool dp[51][1001] = {};

int solve() {
	dp[0][S] = true;;

	for (int i=1; i<=N; i++) {
		for (int j=0; j<=M; j++) {
			if (!dp[i-1][j]) continue;

			int up = j + v_list[i], down =  j - v_list[i];

			if (down >= 0) dp[i][down] = true;
			if (up <= M) dp[i][up] = true;
		}
	}
	
	int ret = -1;
	for (int i=0; i<=M; i++) {
		if (dp[N][i]) ret = i;
	}

	return ret;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	cin >> N >> S >> M;
	for (int i=1; i<=N; i++) cin >> v_list[i];

	cout << solve() << "\n";
}

---

Result : 

Code 1: top-down)   메모리: 2068 KB, 시간: 0 ms

Code 2: bottom-up) 메모리: 2072 KB, 시간: 0 ms

 

Review :

• dp에는 bottom-up 방식만 X
• 재귀를 활용한 top-down 방식도 생각해보기!!