[백준 15732] 도토리 숨기기

 

문제 자체는 이분탐색으로 구현하기 쉬워보이지만

상자의 개수 * 규칙의 개수를 만들어 사용하면 메모리 초과가 난다.

 

별도의 구조체/클래스를 만들어 입력으로 주어지는 A, B, C 를 저장해 O(N) 으로 접근했다.

 

100	110	120	130	140	150
110	125	140

 

예제에 주어진 규칙이다.

도토리는 총 5개이니

100 -> 110 -> 110 -> 120 -> 125 순으로 진행된다.

 

이분탐색할 변수를 두어 3가지 분기로 구현했다.

1. 변수 mid 가 B보다 클때 (위 경우에는 B=150)

  - (B - A)/C + 1 = (150 - 100)/10 + 1 = 6

  - 카운트에 6을 더한다.

2. min가 A보다 작을때는 스킵한다.

3. 그 외의 경우

  - mid - A 가 0일때는 규칙 중 첫번째만 적용된다는 것이므로 1을 더한다.

  - mid - A 가 0이 아닐때는 (mid - A)/C + 1 을 더한다.

 

위 방법을 이용하면 배열에 값을 저장하지 않고도 카운트를 셀 수 있다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int k = sc.nextInt();
        int d = sc.nextInt();
        ArrayList<Box> box = new ArrayList<Box>();
        
        for(int i=0; i<k; i++)
            box.add(new Box(sc.nextInt(), sc.nextInt(), sc.nextInt()));
        
        int left = 1;
        int right = n;
        while(left <= right) {
            int mid = (left + right)/2;
            long cnt = 0;
            for(int i=0; i<box.size(); i++) {
                if(box.get(i).end <= mid)
                    cnt += (box.get(i).end - box.get(i).start)/box.get(i).unit + 1;
                else if(box.get(i).start > mid) continue;
                else
                    cnt += (mid - box.get(i).start) == 0 ? 1 : (mid - box.get(i).start)/box.get(i).unit + 1;
            }
            if(cnt >= d) right = mid - 1;
            else left = mid + 1;
        }
        System.out.println(left);
    }
    
    static class Box {
        int start;
        int end;
        int unit;
        
        Box(int start, int end, int unit) {
            this.start = start;
            this.end = end;
            this.unit = unit;
        }
    }
}