[백준 3020번] 개똥벌레 - java

문제 설명

1. 동굴의 길이  N, 높이 H미터가 주어진다.

2. 동굴의 길이에 맞춰 장애물이 석순 / 종유석 이렇게 번갈아가며 주어진다.

3. 개똥벌레는 그 장애물을 그냥 뿌수고 지나간다.

4. 개똥벌레가 부수는 최소의 장애물 개수와 그 경우가 몇 개인지 구하면 된다.

풀이 과정

 1. 이분 탐색 문제라는데...내가 푼게 이분 탐색이 맞나? 그냥 구현 + DP로 푼 느낌이다.  누적합

 2. 먼저 배열을 하나 만들어서 장애물의 높이에 따른 개수를 가져간다. 예를 들어 2가 입력되면 arr[2]++ 이런식으로.

 3. 그리고 석순 / 종유석 이렇게 번갈아가면서 주어지기 때문에 두 개의 배열은 각각 다르게 설정하고, 번갈아가면서 하나씩 넣어준다.

 4. 입력받은 장애물을 표현하자면 1 5 3 3 5 1 이렇게 주어지는 경우

 

석순      -> arr[1] = 1, arr[2] = 0, arr[3] = 1, arr[4] = 0, arr[5] = 1 이렇게 될 것이고

종유석   -> arr[1] = 1, arr[2] = 0, arr[3] = 1, arr[4] = 0, arr[5] = 1 이렇게 될 것이다.

 

 5. 그렇다면, 개똥벌레가 종유석의 1위치로 지나가는 경우 1을 부수고, 2는 없고, 3을 부수고, 4는 없고, 5는 부술 것이다.

                                 종유석의 3위치로 지나가는 경우 1은 넘어가고, 2는 없고, 3을 부수고, 4는 없고, 5는 부술 것이다.

                                종유셕의 4위치로 지나가는 경우 1은 넘어가고, 2는 없고, 3은 넘어가고, 4는 없고, 5를 부술 것이다.

석순도 마찬가지

 6. 따라서 N의 위치로 개똥벌레가 지나갈 때에는 그 전 배열에 있는 값에 현재 배열의 값을 구하면 될 것이다.

 7. 그렇게 해서 석순 / 종유석의 부수는 배열들을 저장한 후에 그에 맞춰서 구하면 간단하게 구해진다.

 8. 그런데 종유석은 반대로 자라기 때문에 높이에서 값을 빼서 구해주면 된다.

 근데 이건 결국 이분배열을 구하지 않은 것 같은데 간단히 파악하려고 적은 문제가 통과했다. 이유를 모르겠다..

코드