티스토리 뷰

IOI/IOI2020

IOI2020 Day2 mushrooms 풀이

전명우 2020. 9. 24. 22:21

문제 및 채점: oj.uz

 

번호가 0부터 $N-1$까지 매겨진 버섯 $N$ 개가 있다. 버섯은 두 종류로 구분할 수 있는데 눈으로 구분하기 힘들다. 기계를 사용하여 임의의 버섯들을 선택하여 순서를 정해 일렬로 기계에 넣을 수 있다. 기계에 넣으면 인접한 버섯 중에 종류가 다른 경우가 몇 개인지 확인하여 알려준다. 기계를 잘 사용하여 버섯 0과 같은 종류의 버섯 수가 몇 개인지 구하는 문제다.

 

10점 풀이

1 이상 $N-1$ 이하인 $i$에 대해 기계에 $[0, i]$ 순서로 버섯을 넣어 버섯 $i$가 버섯 0과 같은 종류인지 확인할 수 있다. 이때, 기계 사용을 최대 $19999$번 하게 된다.

 

더보기

 

25점 풀이

10점 풀이에서 사용한 질문 형태로 최대 2번 안에 같은 종류를 가지는 버섯 쌍을 찾을 수 있다. 일반성을 잃지 않고 A 종류인 버섯 두 개를 찾았다고 하자. 기계에 $[A, x, A, y]$ 순서로 버섯을 넣고 결과값을 통해 $x$, $y$가 무슨 종류인지 알 수 있다. 만약 기계의 결과값이 0이라면 $x$, $y$는 모두 A 종류가 되고, 결과값이 1이라면 $x$는 A 종류, $y$는 B 종류가 된다. 결과값이 2라면 $x$는 B 종류, $y$는 A 종류가 되고, 결과값이 3이라면 $x$는 B 종류, $y$는 B 종류가 된다. 같은 종류를 가지는 버섯 쌍을 찾았을 때, 1번의 기계 사용으로 2개의 버섯의 종류를 알 수 있다. 이렇게 전체 버섯의 종류를 파악하면 기계 사용을 최대 $2+\lceil\frac{20000-3}{2}\rceil = 10001$번 하게 된다.

 

더보기

 

80.43점 풀이

25점 풀이를 개선해보자. 각 버섯이 어떤 종류인지 구하는 것이 아니라, 버섯 0과 종류가 같은 버섯의 수를 구하는 문제다. 때문에 일정 수준까지 버섯의 종류를 파악하고 그 이후부터는 수만 세면 된다. 한 종류의 버섯을 $K$ 개 찾을 때까지 버섯의 종류 파악을 했다고 하자. $[A, a_1, A, a_2, A, a_3, \cdots, A, a_K]$ 순서로 기계를 사용하고 결과로 $r$ 값을 얻은 경우, $a_i$ 중에서 종류 B인 버섯의 수는 $\frac{r+1}{2}$이며, 반대로 종류 A인 버섯의 수는 $K-\frac{r+1}{2}$임을 알 수 있다. 이때, 최악의 경우 기계 사용 횟수를 제일 적게 할 수 있는 $K$ 값은 137이며, 그때 기계 사용 횟수는 최대 281번이다.

 

더보기

 

92.62점 풀이

80.43점 풀이를 조금 개선해보자. $[A, a_1, A, a_2, A, a_3, \cdots, A, a_K]$ 순서로 기계를 사용하고 결과로 $r$ 값을 얻은 경우, 만약 $r$이 홀수라면 $a_K$는 B 종류이며, $r$이 짝수라면 $a_K$는 A 종류라는 것을 알 수 있다. 추가적으로 기계 사용 하나에 버섯 하나의 종류를 알 수 있다. 즉, 기계를 사용함에 따라 같은 종류인 버섯의 수가 점점 커지게 되기 때문에 뒤로 갈 수록 1번의 기계 사용으로 확인할 수 있는 버섯의 수가 늘어난다. 이때, 최악의 경우 기계 사용 횟수를 제일 적게 할 수 있는 $K$ 값은 81이며, 그때 기계 사용 횟수는 최대 244번이다.

 

더보기

 

100점 풀이

92.62점 풀이를 개선해보자. 그 풀이에서 한 종류의 버섯의 $K$ 개 찾는 과정 중 질문 1번의 기계 사용으로 버섯 2개의 종류를 판별할 수 있었다. 이는 2의 효율을 갖는다고 볼 수 있는데, 이 효율을 늘릴 수는 없을까?

 

Brute Force로 Decision Tree를 잘 만들어보니, 한 종류의 버섯이 3개 이상, 다른 종류의 버섯이 1개 이상인 경우, 2번의 기계 사용으로 버섯 5개의 종류를 판별하는 방법이 있다. 이는 2.5의 효율을 갖으며, 이전 방법보다 더 효율이 좋고, 전체적인 기계 사용 횟수를 감소시킬 수 있다.

 

그러면 한 종류의 버섯이 3개 이상, 다른 종류의 버섯이 1개 이상이 되기까지 어떤 식으로 기계를 사용할까? 이 또한 마찬가지로 Brute Force로 Decision Tree를 잘 만들어보니, 한 번의 기계 사용으로 5개의 버섯이 같은 종류인지 확인하고 그중 하나라도 다른 종류가 있으면 기계 사용을 2번 더 하여 버섯 5개의 종류를 판별하는 방법이 있다.

 

만약 처음 검사하는 5개 중 다른 종류가 하나라도 있으면 그 즉시 한 종류의 버섯이 3개 이상, 다른 종류의 버섯이 1개 이상이 되며, 만약 모두 같은 종류라면 한 번의 기계 사용으로 버섯 5개의 종류를 알 수 있으니 오히려 더 좋은 상황이다.

 

이 방법에서 최악의 경우 기계 사용 횟수를 제일 적게 할 수 있는 $K$ 값은 97이며, 그때 기계 사용 횟수는 최대 226번이다.

 

더보기

 

참고

각 풀이에서 최악의 경우 기계 사용 횟수를 최소화 해주는 $K$ 값은 python으로 프로그래밍하여 구했다. 100점 풀이에서 가장 좋은 $K$를 구하는 python 코드를 첨부하며, 100점 풀이에서 Brute Force로 Decision Tree를 구한 코드도 첨부한다.

 

더보기

 

더보기

'IOI > IOI2020' 카테고리의 다른 글

IOI2020 Day2 mushrooms 풀이  (0) 2020.09.24
IOI2020 Day2 biscuits 풀이  (0) 2020.09.23
IOI2020 Day2 stations 풀이  (0) 2020.09.23
IOI2020 Day1 plants 풀이  (0) 2020.09.22
IOI2020 Day1 tickets 풀이  (0) 2020.09.22
IOI2020 Day1 supertrees 풀이  (0) 2020.09.22
댓글
댓글쓰기 폼