[Baekjoon] DP - 1495 기타리스트 (오답노트)

문제

1495번: 기타리스트

 

풀이

현재 볼륨 = 직전 볼륨 ± 현재 조절할 수 있는 볼륨의 크기이다.

해당 문제는 2개의 변수가 있다.

1. index(마지막까지 연주)

2. 볼륨의 크기

 

이를 만족하기 위해 2중 배열을 생성해야한다.

index와 0부터 최대 볼륨의 크기까지 값을 할당한다.

 

처음 볼륨 크기를 기준으로 현재 볼륨의 크기를 더하거나 빼서 가능한지 확인한다.

이 후, 마지막 배열(마지막 곡 연주)에서 가능한 볼륨의 크기 중 가장 큰 값을 구한다.

 

import sys

n, s, m = map(int, sys.stdin.readline().rstrip().split())
v = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
d = [[0] * (m + 1) for _ in range(n + 1)]


# 현재 볼륨 = 직전 볼륨 ± 조절할 수 있는 볼륨의 크기
# 변수는 2개가 있다.
# 1. index
# 2. 볼륨 조절(+, -)

def solution(s, n, m, v, d):
    # 현재 시작값 볼륨
    d[0][s] = 1

    # 다음으로 조절할 수 있는 볼륨값부터
    for i in range(1, n + 1):
        # 현재 볼륨을 조절할 수 있는 값 구하기
        for j in range(m + 1):
            if d[i - 1][j]:
                plus = j + v[i]
                minus = j - v[i]

                # 볼륨을 더했을 때, 볼륨 조절이 가능한 지 확인
                if 0 <= plus <= m:
                    d[i][plus] = 1
                
                # 볼륨일 뺐을 때, 볼륨 조절이 가능한 지 확인
                if 0 <= minus <= m:
                    d[i][minus] = 1


    # 가능한 볼륨 중 가장 큰 값 찾기
    answer = - 1

    for j in range(m + 1):
        if d[n][j]:
            answer = j

    return answer


print(solution(s, n, m, v, d))

 

채점 결과