9576번 - 책 나눠주기
그리디를 이용해서
원하는 책의 범위가 작은 사람부터 책을 주려는 풀이가 많이 보입니다.
다만 시도해보시면 틀리게 되는데 몇 가지 예시를 들어보겠습니다.
16 61 51 21 23 43 45 6
이런경우를 생각해 봅시다
1~5를 제외하고
나머지 5명은 모두 범위가 2입니다
범위가 작은 사람부터 책을 가져가면 1 2 : 11 2 : 23 4 : 33 4 : 45 6 : 51 5 : x
만약 5 6을 원하는 사람이 6번책을 가져갔다면 1 5 를 원하는 사람은 5번을 가져가서 답이 6가 됩니다.
만약 범위내에서 번호가 큰 책을 가져간다고 한다면 위에 있는 예시를 좌우로 뒤집는거나 마찬가지기 때문에16 62 61 23 43 45 65 6
이런 케이스에서 같은 이유로 틀리게 됩니다.
만약 1 5범위의 책을 원한다면, 3 2 4 1 5 처럼 중앙부터 책을 가져가는 경우는 어떨까요?
17 71 51 21 23 43 45 75 7
이럴경우
1 2 : 11 2 : 23 4 : 33 4 : 45 7 : 65 7 : 51 5 : x비슷한 예제로 틀리게 됩니다.
즉 원하는 책의 범위가 작은 사람부터 책을 주려는 경우 틀리게 됩니다.
댓글을 작성하려면 로그인해야 합니다.
rich1055 2년 전 3
그리디를 이용해서
원하는 책의 범위가 작은 사람부터 책을 주려는 풀이가 많이 보입니다.
다만 시도해보시면 틀리게 되는데 몇 가지 예시를 들어보겠습니다.
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
비슷한 예제로 틀리게 됩니다.
즉 원하는 책의 범위가 작은 사람부터 책을 주려는 경우 틀리게 됩니다.