[그리디 알고리즘] 2847번 - 게임을 만든 동준이

[백준] 2847번 - 게임을 만든 동준이

(풀이1) for문, while문을 다 쓰는 방법

1) 문제 해결 아이디어

아이디어는 쉽게 떠올릴 수 있었다.

 

이 문제의 핵심은 높은 레벨의 점수가 낮은 레벨의 점수보다 항상 높아야 한다는 것이다.

낮은 레벨부터 차례대로 점수가 입력되었기 때문에 검사는 높은 레벨부터 해야한다.

역순으로 검사를 해야하므로 인덱스 처리를 쉽게하기 위해 해당 리스트(score)을 뒤집는다.

 

현재 값이 이전 값보다 크다면 점수가 잘못된 것이므로 점수(socre[i])를 1 감소 시키고 감소횟수(cnt)를 1 증가한다.

 

2) 소스코드

n = int(input())   # 레벨 수
score = [int(input()) for _ in range(n)]  # 레벨 클리어 점수
score.reverse()
cnt = 0    # 감소 횟수

for i in range(1, n):
  # 현재 값이 이전값보다 크다면 1감소 시키기
  while(score[i] >= score[i - 1]):
    score[i] -= 1  # 1을 빼고
    cnt += 1      

print(cnt)

 

(풀이2) for문 1번 쓰는 방법

1) 문제 해결 아이디어

이 방법은 for문을 한번만 쓰기 때문에 상대적으로 더 효율적인 코드라고 할 수 있다.

 

역순으로 검사하기 위해 for문의 시작값을 (n-1), 끝값을 1로, 증감을 -1로 설정하였다.

위의 방식처럼 reverse()하지 않으니 시간이 절약된다.

 

현재값이 이전값보다 크다면 잘못된 것이므로 값을 감소시켜주어야 한다.

감소할 횟수는 이전값에서 현재값을 뺀 것에 1을 더한 값이다.

예를들어, 10 10 이라면 10 9 로 만들기 위해 1번 감소를 진행한다.

최소한으로 감소를 시켜야하기 때문에 현재값을 (이전값 - 1)으로 만든다.

 

여기서 중요한 점은 2줄의 코드 순서가 바뀌면 안된다는 것이다. 아랫 줄에서 점수를 갱신하기 때문에 갱신하기 전에 감소할 횟수를 업데이트 시켜주어야한다.

 

 

2) 소스코드

n = int(input())   # 레벨 수
score = [int(input()) for _ in range(n)]  # 레벨 클리어 점수
cnt = 0    # 감소 횟수

for i in range(n - 1, 0, -1):
  # 현재 값이 이전값보다 크다면 
  if(score[i] <= score[i - 1]):
    cnt +=  score[i - 1] - score[i] + 1
    score[i - 1] = score[i] - 1  
 
print(cnt)

 

[참고] https://velog.io/@jajubal/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EB%B0%B1%EC%A4%80-2847-%EA%B2%8C%EC%9E%84%EC%9D%84-%EB%A7%8C%EB%93%A0-%EB%8F%99%EC%A4%80%EC%9D%B4

[파이썬]백준 2847 게임을 만든 동준이