«   2022/06   »
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30    
Archives
Today
48
Total
86,238
관리 메뉴

차근차근

[백준 1495] 기타리스트 본문

대학교/Algorithm

[백준 1495] 기타리스트

SWKo 2020. 9. 13. 20:55

0. 제목

  • 백준 1495 기타리스트
  • BOJ 1495 기타리스트
  • 파이썬 1495 기타리스트
  • Python 1495 기타리스트

1. 문제

www.acmicpc.net/problem/1495

 

1495번: 기타리스트

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

www.acmicpc.net


2. 풀이

  • 0부터 m까지의 볼륨이 가능하고 각 볼륨에서 출력이 가능하면 True, 불가능하면 False로 설정한다.
  • dp[i][j + 1] : i 번째 노래일 때 j 크기의 볼륨으로 연주 가능한지 여부
  • 노래를 순서대로 확인하며, 매 번 모든 크기의 볼륨에 대하여 검사한다.
  • dp[n]의 원소 값들 중 True이면서 가장 큰 index를 출력한다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
n, s, m = map(int, input().split())  
= list(map(int, input().split()))
 
dp = [[False* (m + 1for _ in range(n + 1)]
 
dp[0][s] = True
 
for i in range(1, n + 1):
    for j in range(0, m + 1):
        if dp[i-1][j] == 0:
            continue
            
        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
 
result = -1
for i in range(m, -1-1):
    if dp[n][i] == True:
        result = i
        break
        
print(result)
    
 

 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 10809] 알파벳 찾기  (0) 2020.10.31
[백준 8958] OX퀴즈  (0) 2020.10.31
[백준 1495] 기타리스트  (0) 2020.09.13
[백준 9251] LCS  (0) 2020.09.12
[백준 11053] 가장 긴 증가하는 부분 수열  (0) 2020.09.12
[백준 12865] 평범한 배낭  (0) 2020.09.11
0 Comments
댓글쓰기 폼