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

문제

https://www.acmicpc.net/problem/1495

1495번: 기타리스트

 

 

풀이

볼륨값을 저장할 집합 d를 선언하고, 볼륨의 값을 업데이트 한다. 

 

예제 1의 동작방식은 아래와 같다. 

• 시작 볼륨이 5이며, 첫번째 볼륨차이는 5이다.
  이때 가질수 있는 볼륨의 값은 0(5-5),10(5+5) 이며 d는 {0, 10}의 값을 가진다.
  이후 d에 있는 모든 값을 다음 볼륨 차이와 계산한다.
• 다음으로 입력된 볼륨 차이는 3이다.
  이때 -3(0-3), 3(0+3), 7(10-3), 13(10+3)의 볼륨을 가질 수 있다.
  하지만 볼륨은 0보다 크고 10(M)보다 작거나 같은 범위를 가지고 있기 때문에 d는 {3, 7}의 값만 가진다.
• 다음으로 입력된 볼륨 차이는 7이다.
  이때 d는 -4(3-7), 10(3+7), 0(7-7),14(7+7) 중 범위에 해당하는 값인 {0, 10}를 값으로 갖는다.
• 입력이 완료되었으므로 현재의 d값{0,10} 중 가장 큰값을 출력한다.  
  만약 범위에 해당하는 값이 없으면 d에는 아무 원소도 들어있지 않게되므로 -1을 출력한다. 

위를 코드로 구현하면 다음과 같다. 

import sys

N, S, M = map(int, sys.stdin.readline().strip().split())
d = {S}

V_list = list(map(int, sys.stdin.readline().strip().split()))

for V in V_list:
    temp = set()
    for volume in d:
        if volume + V <= M:
            temp.add(volume + V)
        if volume - V >= 0:
            temp.add(volume - V)
    d = temp

if not d:
    print(-1)
else:
    print(max(d))

 

 

 

😣덧) 

처음에 리스트로 구현했더니 메모리 초과가 생겼다. 

import sys

N,S,M=map(int,sys.stdin.readline().strip().split(' '))
d=[S]

V_list = [int(x) for x in sys.stdin.readline().strip().split()]
for i in range(1,N+1):
    V = V_list[i-1]
    temp=[]
    for j in range(len(d)):
        if V+d[j]<=M:
            up=V+ d[j]
            temp.append(up)
        if d[j]-V>=0:
            down= d[j] -V
            temp.append(down)
    d=temp


if len(d)==0:
    print(-1)
else:
    print(max(d))

집합은 해시 테이블(hash table)을 사용하여 요소를 저장하므로, 고유한 값만을 저장하고 중복된 값은 무시한다. 이 때문에 리스트보다 메모리를 적게 차지한다!