[usaco] 1.3 Barn Repair - usaco
2009.08.08 22:35 Edit
문제 이해가 안되서 한참동안 들여다봤던 문제이다.
소들이 한줄로 우리안에 들어있고 소들이 들어있는 우리의 번호가 주어진다.
이 때 n개의 문(다양한 길이의 길쭉한)으로 우리를 막는다고 할 때
막히는 우리의 개수는 출력하라는 문제이다.
그냥 생각하면 소들이 들어있는 우리만 막으면 되겠지만 n개의 문으로 막아야하므로
비어있지만 같이 막히는 우리가 생긴다.
이 문제 역시 greedy로
가장 멀리 떨어져있는 우리들 순서로 띄워놓으면 된다.
소들이 한줄로 우리안에 들어있고 소들이 들어있는 우리의 번호가 주어진다.
이 때 n개의 문(다양한 길이의 길쭉한)으로 우리를 막는다고 할 때
막히는 우리의 개수는 출력하라는 문제이다.
그냥 생각하면 소들이 들어있는 우리만 막으면 되겠지만 n개의 문으로 막아야하므로
비어있지만 같이 막히는 우리가 생긴다.
이 문제 역시 greedy로
가장 멀리 떨어져있는 우리들 순서로 띄워놓으면 된다.
