[Baekjoon] 15732: 도토리 숨기기

문제

욕심 그득한 다람쥐가 도토리를 나름 머리써서 숨기는 걸 찾는 문제이다.

 

풀이

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Q15732 {

    static class Dotori {
        private int start;
        private int end;
        private int gap;

        public Dotori(String start, String end, String gap) {
            this.start = Integer.parseInt(start);
            this.end = Integer.parseInt(end);
            this.gap = Integer.parseInt(gap);
        }
    }

    private static List<Dotori> dotoris = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] nkd = br.readLine().split(" ");
        int n = Integer.parseInt(nkd[0]);
        int k = Integer.parseInt(nkd[1]);
        int d = Integer.parseInt(nkd[2]);

        for (int i = 0; i < k; i++) {
            String[] input = br.readLine().split(" ");
            dotoris.add(new Dotori(input[0], input[1], input[2]));
        }

        int left = 1;
        int right = n;
        while (left <= right) {
            int mid = (left + right) / 2;

            long count = 0;
            int dotoriSize = dotoris.size();
            for (int i = 0; i < dotoriSize; i++) {
                int start = dotoris.get(i).start;
                int end = dotoris.get(i).end;
                int gap = dotoris.get(i).gap;

                if (start > mid) {
                    continue;
                }

                if (end <= mid) {
                    count += (end - start) / gap + 1;
                    continue;
                }

                count += (mid - start) == 0 ? 1 : (mid - start) / gap + 1;
            }

            if (count >= d) {
                right = mid - 1;
                continue;
            }
            left = mid + 1;
        }
        System.out.println(left);
    }
}

 

 

이번 스터디 문제였는데, 자꾸 중복된 유형을 계속 내는 것 같아 다른 유형을 내보고자 했다. 그래서 미리 유형을 알고 간 문제라 풀이를 수월하게 할 수 있었다.

 

아마 유형 모르고 했으면 20번 제출했을 것 같다.

 

이 문제의 중점은 먼저 여태 넣은 도토리 개수를 어떻게 찾느냐이다.

아마 DP로 푼 사람이 꽤 있을 것 같은데 이 문제는 그러면 삑나게 처리해버렸다.

 

여기서 유형을 잠깐 언급하자면 이분탐색인데, 유형을 알았다면 생각할 것은 어디를 어떻게 왜 이분탐색으로 처리하는 가이다.

물론 유형을 모른 상태에서 찾아나가봐야한다.

 

이분탐색의 조건은 정렬되어 있는 상태에서 선형탐색보다 빠르게 찾아나가는 탐색 기법이다.

위 문제는 당연히 정렬되어 있기 때문에 적용할 수 있다.

 

그럼 여태 넣은 도토리 개수는 어떻게 아는가?

우리는 예제 입력을 보고 개수를 구하기 위해 떠오른 수식이 있을 것이다! 그걸 활용해보자.

 

100에서 150까지 10간격으로 넣으면? 당연히 5개다. 왜? (150-100) / 10 = 5

모른다면 초등학교 선생님께 자문을 구해보자.

이는 150 이상일 때 적용하고 만약 현재 위치가 100 미만이라면 넣지 않아도 될 것이다.

또 그 사이값이라면 조건을 추가하여 똑같이 수식을 적용해주면 된다.



위 수식을 통해 모든 규칙을 돌며 탐색하면 답을 구할 수 있다.

 

회고

유형을 알고 풀어버렸다. 오랜 시간이 지난 후 다시 풀어봐야겠다.