rich1055   2년 전

그리디를 이용해서 

원하는 책의 범위가 작은 사람부터 책을 주려는 풀이가 많이 보입니다.

다만 시도해보시면 틀리게 되는데 몇 가지 예시를 들어보겠습니다.

1
6 6
1 5
1 2
1 2
3 4
3 4
5 6

이런경우를 생각해 봅시다

1~5를 제외하고

나머지 5명은 모두 범위가 2입니다

범위가 작은 사람부터 책을 가져가면 
1 2 : 1
1 2 : 2
3 4 : 3
3 4 : 4
5 6 : 5
1 5 : x

만약 5 6을 원하는 사람이 6번책을 가져갔다면 
1 5 를 원하는 사람은 5번을 가져가서 답이 6가 됩니다. 

만약 범위내에서 번호가 큰 책을 가져간다고 한다면 
위에 있는 예시를 좌우로 뒤집는거나 마찬가지기 때문에
1
6 6
2 6
1 2
3 4
3 4
5 6
5 6

이런 케이스에서 같은 이유로 틀리게 됩니다.

만약 1 5범위의 책을 원한다면, 3 2 4 1 5 처럼 중앙부터 책을 가져가는 경우는 어떨까요?

1
7 7
1 5
1 2
1 2
3 4
3 4
5 7
5 7

이럴경우

1 2 : 1
1 2 : 2
3 4 : 3
3 4 : 4
5 7 : 6
5 7 : 5
1 5 : x
비슷한 예제로 틀리게 됩니다.

즉 원하는 책의 범위가 작은 사람부터 책을 주려는 경우 틀리게 됩니다.

댓글을 작성하려면 로그인해야 합니다.