[Python] 2872. 우리집엔 도서관이 있어(실2) / 그리디

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

https://www.acmicpc.net/problem/2872

2872번: 우리집엔 도서관이 있어

---

2. 핵심 아이디어

이 문제가 어려운 이유는 어떤 순서로 책을 꺼내야 하는지를 고민하기 때문이다.

그러나, 자세히 잘 바라보면 꺼내는 순서는 이미 정해져 있다.

 

예를 들어 다음 책의 배열이 있다고 가정해보자

5 4 3 2 1

 

이 상황에선 최대값 뒤에 있는 4 3 2 1을 앞으로 꺼내면 된다.

그리고 그 순서는 오름차순에 맞게 알아서 잘 꺼내면 된다.

 

즉, 우리는 이 순서를 앞으로 꺼낼 필요가 있는지 그 당위성을 검증하면 되지

어떤 순서로 꺼내야 할지를 고민할 필요가 없다.

 

그럼 꺼내야할 필요가 있는 숫자, 즉 앞으로 옮길 당위성은 어떻게 확인할 수 있을까?

 

당위성1. 가장 큰 숫자 뒤에 있는 책들은 앞으로 옮겨야 한다.

 

다음 배열들이 있다고 해보자

 

1 3 5 2 4 

1 2 3 6 5 4

1 2 3 4 7 6 5

 

여기서 각 배열 최대값의 뒤에 있는 책들은 오름차순 정렬을 위해

어떻게든 앞으로 보내져야 할 숫자들이다.

 

당위성2. 최대값에 앞에 있는 숫자들 중 가장 긴 내림차순 길이를 구한다.

 

이제 최대값 앞에 있는 숫자들을 살펴보자

 

최대값이 max_number라면 최대값 앞의 숫자들을 역순으로 탐색하며

가장 긴 내림차순의 길이를 생각해보면 된다.

 

예를 들어 다음 배열이 있다고 생각해보자

3 2 4 5 1

 

5앞에 있는 숫자를 역순으로 탐색하며 내림차순이 어디까지 이어지는지 확인해보자

 

5 앞에 4 와 3이 있다.

즉 내림차순으로 가장 긴 배열 길이는 3이다. 다른 말로 이 3가지 숫자는 움직일 필요가 없다.

 

아직 감이 잘 안온다면 다른 예시를 보자

3 2 5 4 1

 

5 앞에 그 아래 숫자인 4가 없다. 앞 숫자들에서 5까지의 연속된 내림차순이 없기 때문에 5를 제외하고 모든 책들을 앞으로 한번씩은 보내주어야 한다.

 

그럼 이런 의문이 들것이다.

아니, 3이랑 2는 최대값 5보다 앞에 있는데 앞으로 옮길 필요가 있는가?

 

우리가 최대값-1부터 역순으로 내림차순을 탐색하는 이유가 있다.

 

이 배열에서 최대값 5 내림차순 다음 숫자인 4는 앞에 존재하지 않는다.

 

3 2 5 4 1

 

따라서 4를 앞으로 보내면

 

4 3 2 5  1

 

이런 순서가 된다. 따라서 3과 2도 옮겨야할 당위성이 생긴다. 계속 옮겨보면

 

   3 2 5 4 1

> 4 3 2 5 1

> 3 4 2 5 1

> 2 3 4 5 1

> 1 2 3 4 5

 

예상했던 대로 5를 제외한 나머지 숫자는 모두 옮겨주었다.

 

당위성 2가지를 살펴보면 다음과 같다.

 

당위성1. 최대값 뒤에 있는 책들은 앞으로 옮겨주어야 한다.

당위성2. 최대값 앞으로 역순으로 내림차순을 탐색하며 가장 긴 배열만큼은 옮겨주지 않아도 된다.

 

그럼 이를 예시에 적용해보자

 

예제 1 : 3 2 1

당위성1. 최대값 3 뒤에 2개가 있다. 이건 무조건 옮겨주어야 한다. 2

당위성2. 최대값 앞에 숫자가 없다. 0 

=> 두개를 더하면 답은 2

 

예제2.  1 3 4 2

당위성1. 최대값 5뒤에 숫자 1개가 있다.  1

당위성2. 최대값 앞에 연속된 내림차순 3 4는 옮겨주지 않아도 된다. 1만 옮겨주면 된다.  1

=> 두개를 더하면 답은 2

---

3. 코드

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

idx= books.index(max(books))

temp= books[:idx][::-1] # 최대값보다 앞에 있는 책들 중 내림차순 확인을 위해 뒤집음

cnt=n-idx-1 # 당위성1. 최대값보다 뒤에 있는 애들은 어차피 올려야 한다.

num= max(books)-1 # 연속된 내림차순 탐색

for i in temp:
  if i==num: # 당위성2. 연속된 내림차순 숫자 확인! => 이건 옮길 필요가 없다.
    num-=1
  else:
    cnt+=1

print(cnt)

---

4.배운 점

그리디 문제는 아이디어가 중요한 만큼 사고의 확장이 필요한 사안인 것 같다. 

그리고 그 사고의 확장은 자신의 실력보다 조금 더 상위의 문제를 풀면서 계속 스트레칭을 하는 방법밖에 없는 것 같다.

 

이 문제에서 나는 당연히 순서를 고려하기 시작하면서 많은 시간을 쏟을 수 밖에 없었다...

그러나, 그리디 문제의 핵심은 문제를 그 자체로 받아들이기 이전에 각 상황의 최선의 선택이 무엇인지 생각하는 것임을 잊지말자.