[baekjoon] 백준 1495번(파이썬): 기타리스트

문제

1495번: 기타리스트

알고리즘

- 2차원 배열을 통해 각 곡마다 볼륨을 저장한다.

- 반복문을 통해 각 곡을 통해 만들 수 있는 볼륨을 dp에 담는다.

- 현재 곡에 볼륨이 담겨있다면 볼륨을 키우거나 줄인 값을 다음 곡에 현재 볼륨을 담는다.

- 모든 곡을 확인했다면 마지막 곡에 최대 볼륨을 출력한다.

코드

import sys

n, s, m = map(int, sys.stdin.readline().split())
v = list(map(int, sys.stdin.readline().split()))
dp = [[0] * (m + 1) for _ in range(n + 1)] # 2차원 배열(각 곡마다 볼륨을 저장)
dp[0][s] = 1

# 반복문을 통해 각 곡을 통해 만들 수 있는 볼륨을 dp에 담는다.
for i in range(n):
    for j in range(m + 1):
        # 현재 i곡의 볼륨이 담겨있다면
        if dp[i][j] == 1:

            # 볼륨을 줄였을 때 0보다 크다면 다음 곡에 현재 볼륨을 담는다.
            if j - v[i] >= 0:
                dp[i + 1][j - v[i]] = 1

            # 볼륨을 키웠을 때 m보다 작다면 다음 곡에 현재 볼륨을 담는다.
            if j + v[i] <= m:
                dp[i + 1][j + v[i]] = 1

# 반복문을 통해 마지막 곡에 최대 볼륨을 찾는다.
for k in range(m, -1, -1):
    if dp[n][k] == 1:
        print(k)
        exit()

# 마지막 곡에 볼륨이 없다면 -1 출력
print(-1)

 

틀린 코드(메모리 초과)

import sys


def music(s, i):
    global v

    if i == n:
        res.append(dp[s])

        return

    if s - v[i] >= 0:
        dp[s - v[i]] = s - v[i]
        music(s - v[i], i + 1)

    if s + v[i] <= m:
        dp[s + v[i]] = s + v[i]
        music(s + v[i], i + 1)


n, s, m = map(int, sys.stdin.readline().split())
v = list(map(int, sys.stdin.readline().split()))

dp = [0] * (m + 1)
res = []


music(s, 0)

if res:
    print(max(res))

else:
    print(-1)

재귀 함수를 통해 볼륨을 키우거나 줄였을 때 저장 가능한 볼륨을 다시 재귀적으로 탐색하여 문제를 수행했고 마지막 곡에 들어온 볼륨 중 최대 값을 출력했다.

많은 계산이 들고 효율적이지 못한 코드라서 메모리 초과가 나오는 것으로 보인다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법