[백준] 1495번: 기타리스트 - 파이썬

📕 문제해석

기타 연주를 하는데 각 곡마다 볼륨을 변경하려고 한다. 곡마다 변경할 수 있는 숫자가 정해져있다. 그 숫자로 현재 볼륨에서 더하거나 뺄 수가 있다. 볼륨이 음수가 나오면 안되고 주어진 볼륨 값을 넘을 수도 없다. 
이때 최대 볼륨은?

 

📖 문제풀이

1. n, s, m과 v를 입력받고 m 길이를 가진 리스트 n+1개를 만든다. (다이나믹 프로그래밍을 위한)
2. 현재 볼륨을 체크한다.
3. 시작 볼륨에서 주어진 v[i]를 더할 수 있다면 더하고 뺄 수 있다면 빼준다. 0<=s+v[i]<= m or 0<=s-v[i]<=m
4. 3번에서 만들어진 볼륨에서 v[i]를 빼거나 더할수 있다면 그렇게 해준다.
5. 가장 마지막 리스트(완곡후 나올 수 있는 볼륨들이 담긴)를 내림차순으로 정렬 후 그 최대볼륨 값을 출력한다.

 

예제 입력 1
3 5 10
5 3 7

dp =[[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]

 

리스트 넘어갈 때마다 가능한 볼륨에서 v[i] 빼거나 더해보고 가능한 값이라면 추가해준다.

💻 코드

# n은 곡의 개수, s는 시작 볼륨, m은 최대 볼륨
n, s, m = map(int, input().split())
# 볼륨 리스트 입력받음
v = list(map(int, input().split()))

# dp 정의
dp = [[0] * (m+1) for i in range(n+1)]

# 처음 시작
# print(dp[0][s])
dp[0][s] = 1

for i in range(1, n+1): # 곡의 개수만큼
    for j in range(m+1): # 최대 볼륨까지 돌면서 현재 볼륨을 찾음
        if dp[i-1][j] != 0: # 볼륨 조절 가능하다면 즉 현재 볼륨 찾기
            if 0<=j+v[i-1]<=m: # 현재 볼륨과 더한 볼륨이 0 <= v <= m 이라면 더해줌
                dp[i][j+v[i-1]]=1
            if 0<=j-v[i-1]<=m: # 현재 볼륨과 뺀 볼륨이 0 <= v <= m 이라면 빼줌
                dp[i][j-v[i-1]]=1

# 볼륨 조절 불가한 경우 -1 출력을 위해 초기값 
ans = -1 
dp = dp[n]
# 최대값 찾기 위해 내림차순으로 for 문
for i in range(m, -1, -1):
    if dp[i]==1: #최대값 발견하면 중단 
        ans = i 
        break 
    # 값중 1이 하나도 없다면 가능한 볼륨이 없는 것이다.
print(ans)

 

문제링크 : 기타리스트

1495번: 기타리스트