[코딩테스트] 백준 2847번: 게임을 만든 동준이

-문제: https://www.acmicpc.net/problem/2847

2847번: 게임을 만든 동준이

풀이 안보고 스스로 푼 문제(이게 얼마만인지)

 

예제2를 보고 i번째 인덱스의 값이 i+1번째 인덱스의 값보다 큰 경우만 계산하면 될 것 같다고 생각했다. 

그래서 if s[i]>s[i+1] 를 생각했고

s[i]는 s[i+1]보다 1만큼 작으면 된다

s[i]를 s[i+1]-1로 만들 때 감소한 만큼을 cnt에 저장한다 

 

-풀이:

 

그런데 위 코드가 예제1번에서는 적용되지 않았다. 

이유를 찾아보니 해당 풀이로 하면 [5,5,5]는 [4,4,5]가 되고 cnt는 2가 되어 정답이 아니다.

그래서 다른 방법을 생각해 보니 인덱스를 n-1부터 시작하면 어떨까 생각했다. 그러면 배열의 값이 모두 같아도 순차대로 나열할 수 있을 것이라 생각이 들었다. 그래서 다음과 같이 작성하고 코드 돌리니 정답이었다. 

 

-정답풀이: 

n=int(input())
s=[]
cnt=0
for _ in range(n):
    s.append(int(input()))  
for i in range(n-1,0,-1):
    if s[i] <= s[i-1]:
        cnt+=(s[i-1]-s[i])+1
        s[i-1]=s[i]-1
            
print(cnt)