[Python] 백준 #1495- 기타리스트 [try_again]

문제

---

1495번: 기타리스트

코드

---

My answer(완전탐색-메모리초과)

import sys
input=sys.stdin.readline

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

for i in range(1,n+1):
    tmp=[]
    for j in dp[i-1]:
        if(j+v[i-1]<=m):
            tmp.append(j+v[i-1])
        if(j-v[i-1]>=0):
            tmp.append(j-v[i-1])
    if(tmp==[]):
        print(-1)
        break
    dp.append(tmp)
if(i==n):
    print(max(dp[n]))

Another answer

import sys
input=sys.stdin.readline

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

dp = [[0] *(m+1) for _ in range(n+1)]
dp[0][s]=1

for i in range(1,n+1):
    for j in range(m+1):
        if(dp[i-1][j]==0):
            continue
        if(j - array[i-1]>=0):
            dp[i][j-array[i-1]]=1
        if(j + array[i-1]<=m):
            dp[i][j+array[i-1]]=1    
result=-1
for i in range(m,-1,-1):
    if (dp[n][i]==1):
        result=i
        break
print(result)

 

풀이

---

우선 내 코드의 첫번째는 문제를 풀긴했는데 dp가 아니라 완전탐색(브루트포스)로 문제를 푼 것같다. 그래서 답은 정확히 나오는데 제출하면 메모리오류가 떴다. 수가 많아지면 브루트포스라서 엄청나게 많은 수들을 리스트에 저장해서 그런 것 같다. dp로는 결국 문제를 못풀어서 다른 사람의 코드를 참고하였다. 

문제푸는 방법은 우선 모든 나오는 볼륨에 대해서 노래가 가능한지를 판단하는 것이다. dp[i][j]에서 i는 노래의순서,j는 볼륨을 나타낸다. 즉 dp[0][1]은 첫번째곡을 볼륨 1로 재생한다는 의미이다. 이렇게 모든 경우를 하고 마지막 dp[n]번째의 볼륨에 따른 노래 가능 여부를 볼륨이 높은 순으로 확인하고 모든 볼륨에 대해서 가능하지 않으면 -1을 출력하고, 하나라도 가능한게 있으면 그 최대볼륨을 출력하고 종료한다. 이렇게 다른 사람의 코드 풀이를 보고 이해하긴했는데, 이렇게보니까 브루트포스랑 뭐가 다른지 모르겠다?? 모든 볼륨에 대해서 한건 나도 똑같은데 왜 내껀 메모리초과가 나왔을까>,, 정확히는 모르겠지만 나는 각각의 볼륨을 하나하나 저장했는데 이건 볼륨의 인덱스에 1을 저장해서 메모리가 차이가 안난건가?>..잘 모르겠다.