• 풀고나면 쉽지만 풀기까지 힘든 문제.
• n을 0~n/2-1로 하지말고 1 ~ n/2 로 하는 방법도 있다. 

문제

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이 때, 개똥벌레가 파괴해야하는 장애물의 최소값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

K번째 수 성공

• INT64_MAX 쓸때는 조심. 중간에 이 값에다가 +1만 하더라도 오버플로우
• 해법 = > 1000000000000000000LL 을 쓰던가 여기서 98765... 을 쓰면 된다. 
• 더하는 경우가 처음에 left = 0 + right = max 밖에 없어서 오버플로우 안 날것 같은데 그래도 몰라서 right - 100 하고 했는데도 오버플로우
• 오버플로우 나는 이유! left + right 할때 오버플로우가 난다. left + (right - left) / 2 를 하면 나지 않는다. 
• 아무생각없이 right 조건에서 sum >= k 이렇게 썼는데 =을 어디다 넣냐는 중요하다. 보통 sum < k 로 left 조건에 =을 떼고 한다. 

• 교훈. 문제는 나한테 있다. 이분 탐색 알고리즘에겐 없다. 
• 처음 0과 마지막 l 을 배열에 넣어야 하는 것을 간과해서 시간을 많이 썼다. 

• 푸는데 3시간 걸렸다. 
• 문제를 잘못읽어서 
• 제대로 읽고 20분 정도만에 fail 코드를 작성했는데 도저히 

• 이 경우를 처리할 방법을 모르겠었다. 

• 좀 더 보니까 알겠다 저 fail 코드에 제일 아래에 쓴 코드 로 바꾸면 된다. 바보다 위는 고려안해도 되네

• 이 분의 코드는 저런 걸 다르게 언더플로우 걱정없이 할 수 있게 쓰는 코드라고 배울 수 있을 것 같다. 

• 아이디어가 중요 . 해서 그건 맨밑에 적겠다.
• lis 구현할 줄 모른다 아직. 연습 
• 재귀로 구현해보자