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

0.  문제 링크

 

 

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

1495번: 기타리스트

---

1.  풀이 방법

 

 

보통 n * (m + 1)의 배열을 만들어서 처리하는 것 같은데, 나는 그러고 싶지 않았다.
BFS와 흡사하지만 DP다.
따라서 m + 1을 n번 반복하는 식으로 풀었다.
최종적으로 n번 반복 후에 dp에 남아있는 값들 중 하나가 결과가 된다.
배열 대신에 check를 사용하여 이미 설정한 볼륨은 넣지 않았고, deque를 사용하여 설정한 볼륨에 대한 정보를 가져왔다.

참고로 다음 연주 시에는 check 변수를 초기화 시켰다.

---

2.  코드

 

 

from collections import deque
[n, s, m], board = map(int, input().split()), map(int, input().split())
dp = deque([s])
for i in board:
    check = set()       # 다음 연주 전에는 방문 리스트를 초기화 해야 함
    for _ in range(len(dp)):        # 기존의 dp 길이만큼 반복함
        s = dp.popleft()        # 현재 볼륨을 받아옴
        for j in [s - i, s + i]:        # s - i와 s + i를 반복함
            if 0 <= j <= m and j not in check:      # 볼륨이 범위 안에 있고, 방문하지 않았다면
                dp.append(j)        # dp에 넣음
                check.add(j)        # check에 넣어서 이미 방문한 볼륨을 방지함
print(max(dp) if len(dp) else -1)

---

3.  마무리