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

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

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

 

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

 

그리디로 해결한 문제.

 

 

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

 

 

 

 

핵심은

 

 

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

 

 

  -  비교했을 때,

 

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

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

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

 

 

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

 

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

    1인 경우 -> 그대로 진행

 

 

 

 

 

이상입니다.

 

감사합니다!

 

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	// 우리집엔 도서관이 있어
	// 구현? 이진탐색?
	public class p2872 {
	static int[] books;
	public static void main(String args[]) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.parseInt(br.readLine());
	books = new int[n];
	for(int i = 0; i < n; i++) {
	int num = Integer.parseInt(br.readLine());
	books[i] = num;
	}
	int start = 1;
	int sum = 0;
	if(n <= 1) {
	System.out.println(0);
	}
	else {
	// 맨 첫 번째 인덱스만 구하기
	if(books[0] > 1) {
	sum += books[0] - 1;
	start = books[0];
	}
	for(int i = 1; i < n; i++) {
	if(start + 1 < books[i]) {
	sum += books[i] - start;
	start = books[i];
	}
	if(start + 1 == books[i]) {
	start = books[i];
	}
	}
	System.out.println(sum);
	}
	}
	}

view raw p2872.java hosted with ❤ by GitHub