아시아-태평양 지역의 자랑거리로 새로 지어진 원형동물원이 있다.

태평양의 작은 섬에 있는 이 동물원은 다음 그림과 같이 동물우리들이 큰 원형의 형태를 이루고 있으며,

이들 각 우리 안에는 고유의 동물 한 마리가 있다.

동물들을 관람하는 아이들에 대하여 가능하면 많은 아이들이 관람을 즐겁게 하도록 하는 일이 주어져 있다.

동물원을 관람하러 온 아이들을 즐겁게 하는 것은 쉬운 일이 아니다.

- 어떤 아이들이 좋아하는 동물도 있고, 어떤 아이들이 무서워하는 동물도 있다.

예를 들어 Alex 는 원숭이와 코알라는 귀여워서 이들 동물을 좋아하지만, 사자는 날카로운 이빨 때문에 싫어한다.

반면에 Polly 는 아름다운 머리털 때문에 사자를 좋아하지만, 코알라는 아주 지독한 냄새 때문에 싫어한다.

아이들이 무서워하는 어떤 동물들을 다른 동물원으로 옮길 수 있는 선택권이 주어져 있다 하자.

너무 많은 동물을 옮기는 것이 좋지 않을 수 있다. 왜냐하면 아이들이 구경할 동물이 없을 수도 있기 때문이다.

가능하면 많은 아이들이 즐거워할 수 있도록 다른 동물원으로 옮길 동물들을 결정하고자 한다.

각 어린이는 동물원의 우리들이 이루는 원의 바깥쪽에 서 있으며, 자기 앞에 있는 연속하는 5 개의 우리에 있는 동물들만 구경한다.

각 어린이가 무서워하는 동물들과 좋아하는 동물들의 목록이 주어져 있다. 어린이는 다음을 만족하면 즐거워한다.

• 자기가 구경하는 동물들 중 자신이 무서워하는 동물이 한 마리 이상 옮겨지든지 혹은

• 자기가 구경하는 동물들 중 좋아하는 한 마리 이상의 동물이 남아 있다.

예를 들어, 어린이들이 좋아하는 동물들의 목록과 무서워하는 동물들의 목록이 아래와 같이 주어져 있다고 하자.

우리 4 와 12 에 있는 동물을 다른 동물원으로 옮긴다고 하자. 그러면 Alex 와 Ka-Shu 는 즐겁다.

왜냐하면, 이들 어린이는 자신이 무서워하는 한 마리 이상의 동물이 없어졌기 때문이다.

또, Chaitanya 는 자신이 좋아하는 우리 6 과 8 의 동물이 남아있기 때문에 즐겁다.

그러나 Polly 와 Hwan 은 자신들이 좋아하는 동물은 모두 옮겨져서 볼 수 없고

또한 무서워하는 동물들은 한 마리도 옮겨지지 않았기 때문에 즐겁지 않다.

그러므로 우리 4 와 12 에 있는 동물을 옮기면 즐거운 아이들은 총 3 명이 된다.

대신에 우리 4 와 6 의 동물을 다른 동물원으로 옮긴다고 하자.

Alex 와 Polly 는 각각 자신이 무서워하는 한 마리 이상의 동물이 없어졌기 때문에 즐겁다.

그리고 Chaitanya 는 좋아하는 우리 6 의 동물이 없어졌지만 좋아하는 우리 8 의 동물을 볼 수 있기 때문에 즐겁다.

마찬가지로 Hwan 은 좋아하는 우리 12 의 동물을 볼 수 있으므로 즐겁다. Ka-Shu 만 즐겁지 않다.

다른 방법으로 우리 13 의 동물만 옮긴다고 하자. Ka-Shu 는 자신이 무서워하는 동물 하나가 없어졌기 때문에 즐겁다.

그리고 Alex 와 Polly, Chaitanya, Hwan 모두 자신이 좋아하는 동물이 한 마리 이상 남아 있어서 즐겁다.

이럴 경우 가장 많은 5 명의 어린이가 즐겁다.

동물원 timer 1s memory 128MB

동물원 1s 128MB