기타리스트 ( 1495 번 )

1495번: 기타리스트

 

---

🧠 알고리즘

• 동적 프로그래밍(Dynamic Programming, DP)

 

✔️ 동작 방식

• dp[i][j] = i번째 곡에서 볼륨 j가 가능한가 여부를 저장하는 2차원 DP 테이블 생성
• 각 곡마다 현재 가능한 볼륨을 기준으로, 다음 곡 경우 체크
• 테이블을 끝까지 채운 후, 마지막 곡(n번째)에서 가능한 최대 볼륨을 찾음

---

 

 

🧾 코드

import sys

def _main(n, s, m):
    v_list = list(map(int, sys.stdin.readline().rstrip().split()))
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    dp[0][s] = 1 # 시작 볼륨
    for i in range(n):
        for j in range(m + 1):
            if dp[i][j] == 1: # 볼륨이 있는 경우
                min_v, max_v = j - v_list[i], j + v_list[i]

                if min_v >= 0: # 최소 불륨이 0 이상 이면
                    dp[i + 1][min_v] = 1
                if max_v <= m: # 최대 볼륨이 임계치를 넘지 않는 경우
                    dp[i + 1][max_v] = 1

    # 마지막 최대 볼륨 리턴
    for idx in range(m, -1 , -1):
        if dp[-1][idx] == 1:
            return idx
    
    return -1


n, s, m = map(int, sys.stdin.readline().rstrip().split())
print(_main(n, s, m))

---

 

 

⏱️ 시간 복잡도

for i in range(n) : 각 단계를 순회 ( 선형 시간 복잡도 )
	for j in range(m + 1) : 각 볼륨을 순회 ( 선형 시간 복잡도 )
    
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )