문제 바로가기
문제:
Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다. 먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다. 곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.
입력:
첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.
출력:
첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.
풀이:
첫 시도
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
#곡의 개수, 시작볼륨, M
N, S, M = map(int,sys.stdin.readline().rstrip().split(" "))
arr =list(map(int,sys.stdin.readline().split(" ")))
dp = [0] * (len(arr)+1)
P = dp[0] = arr[0]
for i in range(1,len(arr)+1):
if 0 < max(dp[i-1]+arr[i-1], dp[i-1]-arr[i-1]) <= M:
dp[i] = max(dp[i-1]+arr[i-1], dp[i-1]-arr[i-1])
print(max(dp))
# 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값1차원 배열을 선언후 하려고 했지만 어림없는 시도였다.
이 문제는 그래프로 보면 약간 트리구조가 나오는것이다.
무슨 뜻이냐면
3 5 10
5 3 7이거일때 시작은 5다 그럼 dp[0][5] 를 1로 바꿔주고 그 다음격차는 처음인 5다
그럼 dp[1][5]과 dp[1][10] 을 체크하고
그 다음은 dp[1][5] 에서 격차 3만큼 dp[1][10] 에서 격차 3만큼 쭊쭊 확인하는 것이다.
이것을 코드로 표현해보겟다.
N, S, M = map(int,sys.stdin.readline().rstrip().split(" "))
arr = list(map(int, input().split()))
dp = [[0] * (M+1) for _ in range(N+1)]
# 시작볼륨 설정
dp[0][S] = 1
for i in range(1,N+1): #곡의 개수 만큼
for j in range(M+1):
# 볼륨이 1이면
if dp[i-1][j] == 1:
# 그 다음 볼륨을 체크한다.
if 0 <= j+arr[i-1] <= M:
dp[i][j+arr[i-1]]=1
if 0 <= j-arr[i-1] <= M:
dp[i][j-arr[i-1]] = 1
for i in range(M, -1, -1):
if dp[N][i]==1:
ans = i
break
print(ans)
그러면 dp가 완성된다
그리고 마지막에 dp를 거꾸로 돌면서
dp[N][i] 가 1이면 정답을 출력해준다. 그 이뉴는
dp[0][S] 부터 출발하므로 결국 마지막곡을 연주를 할 수 있는것이다. 그러니깐 맨 마지막줄 dp[N][i] 가 1 인 것들은
처음부터 기타를 칠 수 있는것이다. 그러므로 i를 거꾸로 내려와서 제일 큰 값을 출력해주면된다.
댓글