1495번 기타리스트

문제

""

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 ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다.
이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력
첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.

 

예제 입력 1
3 5 10
5 3 7
예제 출력 1
10

"""

예제 문제 해결전략

- table의 위치 값이  최대 및 최소 볼륨값이다.  "1"이 2번쨰 위치에 있으면 최소 및 최대 볼륨은 2다!

 

n = 곡의 개수 s = 시작 볼륨 m = 최대 볼륨

n = 3            s = 5            m =10

 

1> 표만들기(m+1개의 행, n+1개의 열) 

 

<볼륨값 = 위치 값>

0

1

2

3

4

5

6

7

8

9

10

 

Q. (m+1)개의 행을 만들까? 

A. 볼륨의 max 가 10이므로 허용 가능한볼륨은 0~ 10까지의 정수. 즉 11개가 필요합니다.

 

Q (n+1)개의 열을 만들까?

A. n =3 즉 3곡을 연주한다고 합니다. 그렇지만 ! 첫 열에는 곡을 치기전 시작 볼륨의 위치를 넣을 것이기 때문에 n+1개의 열을 만듭니다,

첫번째 열은 초기의 볼륨을

두번째 열은 곡번호 1의 볼륨을

세번째 열은 곡번호 2의 볼륨을

세번째 열은 곡번호 3의 볼륨을 넣어 볼륨값의 위치를구하겠습니다.

곡 번호	볼륨
1	5
2	3
3	7

2> 문제에 제시된 초기 단계 볼륨넣기

 

0

1

2

3

4

5

6

7

8

9

10

0	0	0	0	0	1	0	0	0	0	0

Q. 왜 5번쨰 1을 넣었는가?

A. 초기 단계의볼륨은 5라고 예제에 적혀 있습니다

 

위치 값이  최대 및 최소 볼륨값이다

 

3> 1번째 곡 볼륨 넣기

곡 번호	볼륨
1	5

 

0

1

2

3

4

5

6

7

8

9

10

0	0	0	0	0	1	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	1

Q. 왜 1이 0번째하고 10번째에 위치하게 되었는가?

A. 1번쨰 곡의 최대 볼륨변경 값은 5라고 예시에 적혀있습니다. (+-5)따라서 초기 볼륨의값은 5이므로 1번째 값의 최소 볼륨값은 0 최대 볼륨값은 10까지 조정 가능합니다.따라서 0번째 위치에는 1을, 10번째 위치에는 1을 적어둡니다,

 

즉 최소 볼륨량은 0 최대 볼륨량은 10

 

위치 값이  최대 및 최소 볼륨값이다

 

4> 2번째 곡 볼륨 넣기

곡 번호	볼륨
1	5
2	3

 

0

1

2

3

4

5

6

7

8

9

10

0	0	0	0	0	1	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	1
0	0	0	1	0	0	0	1	0	0	0

Q. 왜 3번 7번에 1을 적었는가?

A. 1번째 곡이 끝난 이후 최소 볼륨은 0 최대 볼륨은 10이다

2번쨰 곡의 볼륨 증감량은 3이므로(+-3)

0 + 3 , 10 -3 

즉  1번이 끝난 직후 2번쨰 곡이 갖는

최소 볼륨값은 3 최대 볼륨값은 7이다.

위치 값이  최대 및 최소 볼륨값이다

 

5> 3번째 곡 볼륨 넣기

곡 번호	볼륨
1	5
2	3
3	7

 

0

1

2

3

4

5

6

7

8

9

10

0	0	0	0	0	1	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	1
0	0	0	1	0	0	0	1	0	0	0
1	0	0	0	0	0	0	0	0	0	1

Q. 왜 0번 10번의 값이 1일까

A. 2번째 곡이 끝난후 최소 볼륨값은 3 최대 볼륨값은 7입니다.

3번째 곡의 볼륨 증감량은 7이므로(+-7)

4, 14가 되어야 할것 같지만

 

볼륨값의 한계치(조건에 있다)는 0 ~ 10 사이여서

최솟값은 0 최댓값은 10으로 나타나게 된다

위치 값이  최대 및 최소 볼륨값이다

 

<코드 만들기>

 

n, s ,m = map(int, input().split()) # n = 곡의 개수 s = 시작 볼륨 m = 최대 볼륨   ## n = 3 ,   s = 5 ,   m =10을 넣는다

table = [[0] * (m + 1) for _ in range(n + 1)] # 속성값 0 ~ 10 까지 (max 볼륨을 기준)으로한 표만들기

 

0

1

2

3

4

5

6

7

8

9

10

 

0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0

<분석>

#[0] * (m+1) :  0을 포함하는 m+1개의 열을만들어라  ## m =10이므로 0~ 10 까지는 총 11칸이 필요하다!

#for_in range(n+1) :  행의 갯수가 n+1개인 행이 필요하다. ## n = 3이므로 4개의 행이 필요하다

#table의 인덱스 값이 최대 및 최소 볼륨값이다 

 

array = list(map(int, input().split())) # +-할수 있는 최대값들  ## 1번쨰  +-5,  2번쨰 +-3 , 3번쨰 +-7 을 할 예정입니다. array = [5,3,7]이 들어가겠네요!

 

table[0][s] = 1 # 초기 값의 볼륨의 위치를 표시하자  ## s = 5이므로 table[0][5] = 1 즉 초기에는 5가 최대및 최소 볼륨값

0

1

2

3

4

5

6

7

8

9

10

0	0	0	0	0	1	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0

 

곡 번호	볼륨
1	5
2	3
3	7

 

<반복문 전체 코드>

for i in range(1, n + 1): 
    for j in range(m + 1): 
        if table[i-1][j] == 0:
            continue                   
             
        if j + array[i-1] <= m:
            table[i][j + array[i-1]] = 1
            
        if j - array[i-1] >= 0:
            table[i][j - array[i-1]] = 1

 

 

<반복문 분석>

for i in range(1, n + 1):         ## 곡번호 1 번 2 번 3번 ## 행을 반복
    for j in range(m + 1):       ## 0 ~ 10번 까지 j값이 왔다갔다한다. (열을반복)

        if table[i-1][j] == 0:      ##  해당 table 값이 0이면 넘겨
            continue

        if j + array[i-1] <= m:
            table[i][j + array[i-1]] = 1

 

#i=1 일때 table 진행상황 j = 0  1번째 if 성립 continue(다음번 j로 건너뛰기)

0	0	0	0	0	1	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0

#i=1 일때 table 진행상황 j = 1 ,  1번째 if 성립 continue(다음번 j로 건너뛰기)

0	0	0	0	0	1	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0

.

.

 

.

#i=1  j = 5일때            2, 3번쨰 if 성립

    if j - array[i-1] >= 0:
        table[i][j - array[i-1]] = 1   

 

# i =1일때 j = 5일떄 , array= [5, 3, 7] ,   5  - array[0] = 5 -5 =0 이므로 if조건 성립

따라서 table[1][0] 자리에 1을 넣자.

0	0	0	0	0	1	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	1
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0

 

for i in range(1, n + 1): 
    for j in range(m + 1): 
        if table[i-1][j] == 0:
            continue                   
             
        if j + array[i-1] <= m: # array = [5,3,7]
            table[i][j + array[i-1]] = 1
            
        if j - array[i-1] >= 0:
            table[i][j - array[i-1]] = 1

 

# i=2일때 j = 0 일떄 

0	0	0	0	0	1	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	1
0	0	0	1	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0

 

# i =2 일때 j = 10 일떄

0	0	0	0	0	1	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	1
0	0	0	1	0	0	0	1	0	0	0
0	0	0	0	0	0	0	0	0	0	0

 

# i=3 일때도 반복 if문 실행!

#결과값

0	0	0	0	0	1	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	1
0	0	0	1	0	0	0	1	0	0	0
1	0	0	0	0	0	0	0	0	0	1

 

## 대부분 1번쨰 if문에서 continue 된다!

## 2번쨰 3번쨰 if문은 1번쨰 if문을 만족하지 않는 상태!(elif 로도 만들수 있지 않을까?)

 

# 

result = -1

for i in range(m, -1, -1): # max 값 부터 -1씩 빼서 1이 포함된 위치를 찾자 ## 10 9 8 7 6 5 4 3 2 1 0  위치 까지 찾으면서 1 찾기 
    if table[n][i] == 1:
    result = i
    break

print(result)

 

>>전체코드

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

array = list(map(int, input().split())) 

table = [[0] * (m + 1) for _ in range(n + 1)] 

table[0][s] = 1

for i in range(1, n + 1): 
for j in range(m + 1):

if table[i-1][j] == 0:
continue

if j - array[i-1] <= m:
table[i][j + array[i-1]] = 1

if j - array[i-1] >= 0:
table[i][j - array[i-1]] = 1 


result = -1
for i in range(m, -1, -1):
if table[n][i] == 1:
result = i
break

print(result)