백준 1495 : 기타리스트

카테고리 없음

by qkrtnals 2025. 1. 31. 23:47

💡기본 정보

유형
: DP
풀이 날짜
: 2025년 01월 31일
풀이방법 한줄 요약
: bottom-up형식으로 점화식을 활용해서 범위 동안 반복문 사용

💡문제에서 구해야 할 것

기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있음 .
공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었음.
이 리스트를 V라고 했을 때 V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있음
현재 볼륨이 P이고 지금 i번 째 곡을 연주하기 전이라면 i번 곡은 P+V[i] 나 P-V[i]로 연주해야함

하지만 0보다 작은 값으로 볼륨을 바꾸거나 M보다 큰 값으로 볼륨을 바꿀 수 없음
곡의 개수 : N
시작 볼륨 : S
최댓값 : M
N,S,M이 주어졌을 때 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램. 모든 곡은 리스트에 적힌 순서대로 연주해야함
- 입력 : 첫째 줄에 N,S,M이 주어짐
둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어짐 이 값은 1보다 크거나 같고 M보다 작거나 같음
- 출력 : 첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력
만약 마지막 곡을 연주할 수 없다면 -1을 출력

💡알고리즘 설계

- Bottom-up 방식으로 반복문 구현
- 이전 곡에서 볼륨 P가 가능한경우 P+V[i]나 P-V[i]가 가능한 상황
- dp[N][i]가 1인 값들 중 최댓값 출력

💡CODE

const fs = require("fs");
const input = fs.readFileSync(0,"utf8").toString().split("\n");
const [N,S,M]=input[0].split(" ").map(Number);
const V = input[1].split(" ").map(Number);
let answer = -1; 
const dp = Array.from(Array(N+1),()=>Array(M+1).fill(0));

dp[0][S]=1;
for(let i =1; i<N+1;i++){
    for(let P = 0; P<=M;P++){
        if(dp[i-1][P]){
            if(P-V[i-1]>=0)dp[i][P-V[i-1]]=1;
            if(P+V[i-1]<=M)dp[i][P+V[i-1]]=1;
        }
    }
}

for(let i = 0; i<=M;i++){
    if(dp[N][i])answer=Math.max(answer,i);
}
console.log(answer);

💡시간복잡도