(JAVA) 백준 2872번 : 우리집엔 도서관이 있어

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

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

 

이진 탐색 분류로 되어있는데

 

그리디로 해결한 문제.

 

 

생각보다 쉽지만 처음 규칙을 찾는데 조금 걸렸다.

 

 

 

 

핵심은

 

 

  -  시작 인덱스를 1로 가정하고, 입력받은 책의 맨 앞에서부터 끝까지 하나씩 시작 인덱스와 비교한다.

 

 

  -  비교했을 때,

 

    ->  시작 인덱스 + 1 보다 더 크다면 -> 해당 값 과 시작 인덱스 차이만큼 별도 값에 더한 후, 시작 인덱스를 해당 값    으로 변경한다.

    ->  시작 인덱스 + 1 인 경우 -> 시작 인덱스를 해당 값으로 변경한다.

    ->  시작 인덱스 보다 작은 경우 -> 무시하고 다음 값을 비교하러 간다.

 

 

  -  이 때, 첫 번째 값만 다르게 비교하는데

 

    2보다 큰 경우 -> 첫 번째 값 - 1 한 값을 별도 값에 더한 후, 시작 인덱스를 해당 값으로 변경한다. 

    1인 경우 -> 그대로 진행

 

 

 

 

 

이상입니다.

 

감사합니다!

 

 

소스코드

---