알고리즘 공부

DP공부를 하던 중 처음으로 실버에서 막혔다. 약 1시간정도 고민했는데 못풀고 구글링을 해보니 구글에도 파이썬 풀이는 나오지 않더라 .. 결국 자바 메커니즘 보고 해결! 한 번 안보이면 끝까지 안보이더라ㅋㅋㅋㅠㅠ 혹시 나같은 사람을 위해 벨로그에 풀이를 남긴다!<

아마 카테고리가 이분탐색이 아니었다면 전혀 생각하지 못했을거다. 답으로 구해야 하는 최댓값을 중간값으로 설정해 이분탐색 했다. 풀이 0과 마지막 지점인 distance(25)를 가지고 가운데 값인 12로 답을 정하고 시작한다.문제의 답이 12라면 바위를 n개 제거했을

이 문제의 핵심 이긴사람과 진사람을 나눠서 set집합으로 설정한다는 것! 그리고 1번에게 진 사람은 1번을 이긴사람한테도 반드시 진다! 1번을 이긴 사람과 진 사람을 합치면 n-1이라는 것! 풀이 코드