BOJ(기타리스트) 1495

작성일 | In

1495 기타리스트

  • 첫 볼륨 S
  • 연주해야 하는 곡의 개수 N개
  • 가능한 볼륨의 범위 : 0~M
  • i번 곡을 연주하기 전에 볼륨을 V[i]만큼 바꿔야 한다
  • i번 곡을 연주하기 직전 볼륨이 P라면
  • i번 곡은 P+V[i] 또는 P-V[i]로 연주해야 한다

  • 마지막 곡을 연주할 수 있는 볼륨 중 최댓값

  • 첫 볼륨 S
  • S+V[1] ,S-V[1]
  • S+V[1]+V[2],S+V[1] -V[2]
  • S-V[1]+V[2], S-V[1] -V[2]

  • 1번 2가지, 2번 4가지 해서 총 N번이라면 2^n가지

  • 가능한 볼륨의 범위가 0부터 M까지로 정해져있기 때문에 중복되는 것과 범위를 제외해주면
  • M+1가지를 넘을 수가 없다.
  • 실제로는 N이 커서 모든 방법을 다 할 수 없 지만

  • 제한이 있기 때문에 이 문제는 적용이 가능하다

  • D[i][j] = i번 곡을 볼륨 j로 연주할 수 있으면 1 없으면 0

  • D[i][j]가 1이면
  • D[i+1]j+V[i+1]]와 D[i+1]j-V[i+1]]을 1로 만들 수 있다.
n,s,m = map(int,input().split())
a = [0] + list(map(int,input().split()))
d = [[False]*(m+1) for _ in range(n+1)]
d[0][s] = True
for i in range(n):
    for j in range(m+1):
        if d[i][j] == False:
            continue
        if j-a[i+1] >= 0:
            d[i+1][j-a[i+1]] = True
        if j+a[i+1] <= m:
            d[i+1][j+a[i+1]] = True
ans = -1
for i in range(m+1):
    if d[n][i]:
        ans = i
print(ans)

참고자료 codeplus

0%