1495번 기타리스트

문제

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

1) BFS

범위에 해당하면 큐에 집어넣어서 다음 레벨에서 연산할 수 있도록 한다.

트리 형태로 가능한 모든 경우의 수에 대해 뻗어가는 형식이다. (유사한 아이디어의 문제로는 타겟넘버가 있다)

이때, visited 처리로 동레벨에서의 중복 연산을 제거해야 메모리 초과없이(최악의 경우 2의 50제곱) 동작할 수 있다.

코드

from collections import deque
import sys
input = sys.stdin.readline

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

queue = deque([(s, 0)])  # 현재값, 레벨
prev = 0  # 기존 레벨
for i in range(n):
    d = v[i]
    visited = set()  # 동레벨 내에서 중복 연산 제거 (->없으면 메모리 초과 발생)
    while queue and queue[0][1] == prev:
        cur, l = queue.popleft()
        if cur - d >= 0 and cur - d not in visited:
            queue.append((cur - d, l + 1))
            visited.add(cur - d)
        if cur + d <= m and cur + d not in visited:
            queue.append((cur + d, l + 1))
            visited.add(cur + d)
    prev += 1

print(max(list(map(lambda x: x[0], queue)))) if queue else print(-1)

2) DP

첫번째 방식으로 풀고 알고리즘 분류를 봤는데 다이나믹 프로그래밍이길래(??!!) 신봉선 ㄴㅇㅁㅇㄱ 짤 시전..

- dp[i][j] : i번째 레벨에서 j라는 수를 만들 수 있는가? 

dp 테이블을 이렇게 정의할 수도 있구나 개인적으로 흥미로웠다. 문제 영역을 어떻게 선정하냐에 따라 DP를 활용해서 풀 수 있는 문제가 많구나 싶다..!!

이 경우에는 n(최대 50) * m(최대 1000) 이라는 메모리 공간이 만들어지니 그렇게 크지도 않다.

코드

import sys
input = sys.stdin.readline

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

dp = [[False] * (m + 1) for _ in range(n + 1)]
dp[0][s] = True
for i in range(1, n + 1):
    for j in range(m + 1):
        if dp[i - 1][j]:
            if j - v[i - 1] >= 0:
                dp[i][j - v[i - 1]] = True
            if j + v[i - 1] <= m:
                dp[i][j + v[i - 1]] = True

res = -1
for k in range(m + 1):
    if dp[n][k]:
        res = k
print(res)