11497번
-
[백준 11497번] 통나무 건너뛰기(자바)Algorithm/Greedy Algorithm 2022. 3. 17. 20:08
백준알고리즘 11497번 : 통나무 건너뛰기 두 통나무 간의 최대 높이의 차를 최소한으로 줄여야하는 문제이다. 다만 통나무가 원형으로 이어져있으므로 단순 정렬만으로는 N[0] 과 N[N.length-1] 간의 차이가 극대화되므로 오답이 발생한다. 나는 통나무간의 간격을 줄이기 위해서는 최저점 N[0]과 최고점 N[N.length-1] 간의 지점들을 두 부류로 나누어서 찾아야한다고 생각했다. 즉 최저점과 최고점을 연결하는 선이 두개가 되도록 해야, 최대 높이의 차를 줄일수 있다고 판단하였다. 따라서 N[0], N[2], N[4] ... N[N.length-1] 간의 비교와 N[0], N[1], N[3] ... N[N.length-1] 간의 비교를 동시에 해주도록하였다. 풀이 과정 1. 통나무 목록을 오름차..