1495 기타리스트

💡문제 분석 요약

• 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 찾는다.
• 볼륨은 0 이상 M 이하의 값만 가능하다.
• 각 곡을 연주할 때, 주어진 볼륨 변화(V[i])로만 조절할 수 있다.

💡알고리즘 설계

• 2차원 배열 dp[i][j]를 정의하여, i번째 곡을 연주할 때 볼륨이 j인 상태를 기록.

💡코드

n, s, m = map(int, input().split())
v = list(map(int, input().split()))

def max_volume(n, s, m):
    # dp[i][j]는 i번째 곡을 연주할 때 볼륨이 j인 상태를 나타낸다.
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # 시작 볼륨 설정 : dp[0][S] = True
    dp[0][s] = True

    for i in range(n):
        for j in range(m + 1):
            if dp[i][j]: # 현재 i번째 곡을 연주할 때 볼륨이 j인 상태인지 확인
                if j + v[i] <= m: # 볼륨을 증가시키는 경우 (단, 최대 볼륨 M을 넘지 않아야 함)
                    dp[i + 1][j + v[i]] = True
                if j - v[i] >= 0: # 볼륨을 감소시키는 경우 (단, 최소 볼륨 0보다 작지 않아야 함)
                    dp[i + 1][j - v[i]] = True

    # 마지막 곡의 가능한 볼륨 중 최대값 찾기
    for vol in range(m, -1, -1):
        if dp[n][vol]:
            return vol

    # 가능한 볼륨이 없으면 -1 반환
    return -1


print(max_volume(n, s, m))

💡시간복잡도

• 곡의 개수 N에 대해 각 볼륨 상태를 M까지 확인하므로 O( N * M )

💡 틀린 이유

• 중간에 가능한 볼륨 조절을 고려하지 않아서 모든 상태를 탐색하지 않았거나 초기 조건 및 전이 조건에서 누락된 부분이 있을 가능성.

💡 틀린 부분 수정 or 다른 풀이

• 볼륨 조절의 모든 가능한 상태를 고려.

💡 느낀점 or 기억할정보

• 다시 풀어볼 것.