BOJ : 기타리스트 [1495]
1. 문제
Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.
먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.
곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.
Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.
먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.
곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.
출처 : https://www.acmicpc.net/problem/1495
2. 아이디어
- 교차 업데이트
3. 코드
mine
s, m = map(int, input().split())
lst = list(map(int, input().split()))
dp1 = [0 for i in range(m + 1)]
dp2 = [0 for i in range(m + 1)]
dp1[s] = 1
for v in lst:
for i in range(m + 1):
if dp1[i]:
if i + v <= m:
dp2[i + v] = 1
if i - v >= 0:
dp2[i - v] = 1
dp1 = dp2
dp2 = [0] * (m + 1)
ans = -1
for i in range(m, -1, -1):
if dp1[i]:
ans = i
break
print(ans)
Author And Source
이 문제에 관하여(BOJ : 기타리스트 [1495]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@onejh96__/BOJ-기타리스트-1495
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 교차 업데이트
mine
s, m = map(int, input().split()) lst = list(map(int, input().split())) dp1 = [0 for i in range(m + 1)] dp2 = [0 for i in range(m + 1)] dp1[s] = 1 for v in lst: for i in range(m + 1): if dp1[i]: if i + v <= m: dp2[i + v] = 1 if i - v >= 0: dp2[i - v] = 1 dp1 = dp2 dp2 = [0] * (m + 1) ans = -1 for i in range(m, -1, -1): if dp1[i]: ans = i break print(ans)
Author And Source
이 문제에 관하여(BOJ : 기타리스트 [1495]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@onejh96__/BOJ-기타리스트-1495저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)