백준 2872 파이썬

생각보다 빠르게 푼 문제!

최근에 알고리즘 스터디에서 그리디를 했어서 그런지 문제를 보자마자 그리디라는 느낌이 왔다.

그렇다면 어떤 부분을 욕심낼까? 를 찾아야 한다는 생각이 들었다. 

최대한 적게 책을 움직이는 것이 욕심내야 하는 포인트이기 때문에 어디까지 정렬했는지를 기준으로 횟수를 세야겠다고 생각했다.

 

👼🏻 구현한 코드

import sys

input = sys.stdin.readline

n = int(input())
books = [
    int(input())
    for _ in range(n)
]

ans = 0
min_book = 1 #어디까지 정렬했는지 확인

for i in range(n):
    if books[i] - min_book == 0 or books[i] - min_book == 1:
        min_book = books[i]
        continue
    elif books[i] - min_book < 0:
        continue
    else:
        ans += (books[i] - min_book)
        min_book = books[i]

print(ans)

 

min_book 은 현재 어디까지 정렬했는지를 나타내는 변수이다.

for 문을 돌면서 min_book 과 books[i] 가 같거나 차이가 1이라면 따로 정렬할 필요가 없으므로 "여기까지 정렬했어"라는 의미에서 min_book 을 업데이트 해주고 continue 한다. 

min_book 이 books[i] 보다 크다는 것은 books[i] 가 이미 정렬이 된 책이라는 뜻이므로 (books[0]~books[i-1] 이 정렬된 상태이므로) 그냥 continue 해준다.

그 이외의 경우에는 아직 정렬이 안된 것이므로 books[i] 와 min_book 을 뺀 것을 ans 에 더해준다.

이렇게 해야 하는 이유는 3 1 2 와 같이 정렬된 경우에는 3-1, 즉 2번으로 정렬할 수 있고, 4 1 3 2 인 경우에는 4-1, 즉 3번만에 정렬이 가능하기 때문이다.