DP_기타리스트_백준_1495

-문제-

 

-문제 접근-

 

이 문제는 각 곡마다 볼륨을 바꿀 수 있는 두 가지 선택(더하거나 빼기)을 이용하여, N개의 곡을 순서대로 연주할 때 마지막에 도달할 수 있는 볼륨 중 최댓값을 구하는 문제입니다. (단, 항상 볼륨은 0 이상 M 이하)

 

입력:

• N: 연주할 곡의 개수
• S: 시작 볼륨
• M: 최대 볼륨
• V[1…N]: 각 곡 전에 조절할 수 있는 볼륨 차이

규칙:

• i번째 곡을 연주하기 전, 현재 볼륨 PPP가 있다면 두 가지 선택이 있음:
  • 볼륨을 P + V [i] 로 변경
  • 볼륨을 P − V [i] 로 변경
• 단, 변경된 볼륨은 반드시 0 이상 M 이하여야 함

출력:

• 모든 곡을 순서대로 연주한 후, 가능한 볼륨들 중 최댓값
• 만약 어떤 선택을 해도 중간에 범위를 벗어나서 연주할 수 없는 경우가 있다면, -1 출력

DP정의:

dp[j] : 현재까지 연주한 곡들에서 볼륨 j가 가능하면 true, 아니면 false

 

초기 상태: dp[S] = true

 

점화식 도출:

각 곡마다 볼륨 변화값 V [i]가 주어지므로, 이전 상태에서 가능한 모든 볼륨 j에 대해 아래의 두 가지 선택지가 있습니다:

• 볼륨 증가:
  만약 현재 볼륨이 j이고 j + V [i] 가 M 이하라면, i번째 곡 후에 볼륨 j + V [i] 가 가능해집니다.  next_dp [j + V[i]] = true;

 

• 볼륨 감소:
  만약 현재 볼륨이 j이고 j − V [i] 가 0 이상이라면, i번째 곡 후에 볼륨 j − V [i] 가 가능해집니다. next_dp [j - V[i]] = true;

 

-전체 코드-

 

-코드 설명-

 

현재 상태(dp 배열):
현재까지 연주한 곡들 후에 도달할 수 있는 볼륨 상태를 기록하는 배열이며 dp [j] 가 true이면 지금까지의 곡들에서 볼륨 j에 도달할 수 있다는 의미입니다.

 

 

다음 상태(next_dp 배열):
현재 곡에서 볼륨 변화(V[i])를 적용한 후, 다음 곡을 시작하기 전에 도달할 수 있는 볼륨 상태들을 저장하는 배열입니다.

 

상태 전이:
현재 상태(dp)에서 가능한 볼륨 j가 있으면, 현재 곡의 볼륨 변화 V[i]를 사용해 j+V[i]와 j-V[i]라는 두 가지 새로운 볼륨 상태를 만들 수 있으며 이 값들이 0 이상 M 이하의 범위 내에 있어야 합니다.

 

외부 반복문 (for (int i = 0; i < N; i++)):

각 곡마다 볼륨 상태 갱신하며 i번째 반복은 i번째 곡을 연주하기 전에 볼륨을 조절하는 단계를 의미합니다.

 

내부 반복문 (for (int j = 0; j <= M; j++)):

dp 배열의 각 인덱스 j를 순회하면서, 만약 dp[j]가 true라면 
현재 곡에서 볼륨을 바꿔서 도달할 수 있는 새로운 볼륨 상태를 계산합니다.

 

dp[j] = next_dp[j]; :

next_dp에 저장된 가능한 볼륨 상태들을 dp 배열로 복사합니다.
즉, dp 배열을 새로 갱신하여 현재 곡에서 얻은 상태가 다음 곡의 초기 상태가 됩니다.

 

answer = j; :

j가 증가하는 순서대로 업데이트되므로 마지막에 최대값이 저장됩니다.

 

 

 

 

 

-END-