반응형 알고리즘/USACO 문제 풀이 썸네일형 리스트형 USACO 2020 US Open Contest [Bronze] 풀이 1. [BOJ 18880] Social Distancing I Gold V [문제 설명] 일렬로 N개의 공간이 있고, 각 공간은 소가 들어있거나(1) 들어있지 않다(0). 그리고 빈 두 공간을 골라 소를 넣어주는데, 이때 소가 들어있는 두 공간 사이의 간격의 최솟값을 D라고 하면 D가 최대가 되어야 한다. [풀이] Case work 문제이다. 경우들을 잘 처리해주어야 한다. 지금부터 말하는 '구간'은 소가 배정되어있지 않은 연속된 공간을 의미한다. 우선, 가장 긴 구간에서 하나를 뽑아서 구간을 나눈 후, 다시 가장 긴 구간에서 하나를 뽑는 것이 최적일 것이라고 생각할 수 있다. 하지만 이 문제에서는 공간을 두 개 고르기 때문에 단순히 이 방식으로는 D를 최대로 만들지 못한다. 예를 들어 1, 10, 13.. 이전 1 다음
