백준 2847 : 게임을 만든 동준이

문제 링크

풀이

(1) 모든 레벨은 항상 동차없는 오름차순이 되어야 합니다. (2) 단, 동차없는 오름차순을 만들기 위해 특정 레벨을 증가시키는 대신 감소시켜서 오름차순으로 바꾸어줍니다.

테스트케이스

• 처음 level

  4 5 3 7 5

• 바뀐 level

  2 3 4 5

• 출력

  6

해당 예제 테스트케이스로부터 level[i-1]은 항상 level[i]보다 작아야 한다고 생각했고, 최소한으로 감소시켜야 하므로 정확히 1만 작으면 된다고 생각했습니다.

• 처음 level

  4 5 3 7 4

• 바뀐 level

  1 2 3 4

• 출력

  9

위의 테스트케이스는 하나만 바꿔볼까 싶어서 넣어본 테스트케이스인데, 운좋게 좋은 케이스가 입력되었습니다. 위의 입력은 다음의 순서로 1 2 3 4 로 바뀌어야 할 듯 합니다.

5 3 7 4
2 3 3 4
1 2 3 4

이 동작을 구현해주기 위해서 (1) level이 동차 없는 오름차순으로 정렬되어있는지 여부를 파악하는 함수를 만들어주었고, (2) level[i-2]가 level[i-1]과 같은 경우에는 level[i-2]에서 하나를 빼주는 if문을 추가했습니다.

코드

def isSorted(arr) :
  for i in range(1,len(arr)) :
    if(arr[i-1] < arr[i]) :
      continue
    else :
      return False
  return True

N = int(input())
level = []
for _ in range(N) :
  level.append(int(input()))

ans = 0
while(isSorted(level) is False) :
  for i in range(1, N) :
    if(level[i-1] >= level[i]) :
      origin = level[i-1]
      level[i-1] = level[i]-1
      diff = origin - level[i-1]
      ans += diff
      if(i >= 2 and level[i-2] == level[i-1]) :
        level[i-2] -= 1
        ans += 1

print(ans)

코드리뷰

해당 블로그의 게시물을 확인해보고 제 코드와의 차이를 찾아보았습니다.

1. for i in range(N-1, 0, -1)
   • range는 range(시작 숫자, 종료 숫자, step)으로 이루어집니다. 즉 위의 코드는 배열을 역순으로 살펴보고 있습니다.
   • 제 코드의 경우에는 앞에서부터 감소시켜주느라, 앞과 현재에서 동차가 발생하고 있었습니다.
   • 뒤에서부터 본다면, 감소만을 사용하고 있으므로 동차가 발생하지 않을 것입니다. 진정한 그리디입니다.
   • 만약 증가를 사용해서 오름차순으로 만든다면, 앞에서부터 보는게 맞겠습니다. 무조건 직전의 수보다 크면 반드시 오름차순으로 정렬되기 때문입니다.
   • 제 코드의 경우에는 앞에서부터 보며, 앞의 배열값과 현재값을 비교하고 있었습니다. 이 경우에는 무조건 앞의 수보다 작다고 해서 직전의 수보다 크다는 보증이 안생기는 까닭입니다.
   • 증가인지, 감소인지, 오름차순인지, 내림차순인지에 대해 알고리즘이 확실하게 달라지고, 효율성도 달라질 수 있다는 점을 배웠습니다.