| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 138 | 48 | 47 | 43.119% |
이 문제는 함수 구현 문제입니다.
경곽이는 오랜 역사와 전통을 자랑하는 국내 최고의 박물관인 'Dinosaur Museum'의 주인이다. 경곽이는 다가오는 $K + 1$번째 겨울 시즌을 기념하여 박물관에서 축제를 개최하였다. 축제가 일어난다는 소식을 듣고 전국 각지에서 온 $N$명의 관람객들이 줄을 서 박물관에 입장하려 한다.
$3$년 만에 겨울 축제를 개최하게 된 경곽이는 박물관을 찾아주는 관람객들을 위하여 입장료 면제 이벤트를 열었다. 우선, 경곽이는 줄을 선 관람객들의 눈을 안대로 가린 후 각 사람에게 지금까지 박물관이 맞은 겨울 시즌을 상징하는 $1$번부터 $K$번까지의 모자 중 하나를 무작위로 씌워준다. 이때, 각 모자는 충분히 많으며 각 관람객에게 특정 모자를 씌워줄 확률은 모두 $\frac{1}{K}$로 동일하다. 모자를 모두 씌우고 난 후 관람객들의 안대를 회수해 각 관람객들이 자신의 모자를 제외한 다른 모든 관람객들의 모자를 확인하게 해준다. 그 후 한 명씩 임의의 순서로 박물관에 입장하면, 관람객들에게 자신이 쓰고 있는 모자의 번호인 것 같은 $1$부터 $K$까지의 수를 하나 적어 다른 관람객들이 볼 수 없게 경곽이에게 제출한다. 경곽이는 모든 관람객이 자신의 모자 종류를 정확히 적을 경우 모두의 입장료를 면제해 주고자 한다.
경곽이가 개최하는 이벤트를 들은 관람객들은 머리를 모아, 입장료를 내지 않아도 될 확률을 최대화하고자 한다. 관람객들을 도와 최선의 전략으로 관람객들이 경곽이에게 제출할 수를 알려주자.
함수 구현에 앞서 #include "festival.h"를 통해 "festival.h" 헤더 파일을 포함해야 한다.
여러분은 아래 함수를 구현해야 한다.
int answer(int N, int K, int i, std::vector<int> v);각 입력은 독립적인 최대 $100$개의 테스트 케이스로 이루어진다. 각 테스트 케이스별로 answer 함수가 각 관람객마다 $1$번씩 총 $N$번 호출된다. answer 함수가 테스트 케이스 순서대로 호출된다는 보장은 하지 않지만, 지문에서 제시된 방식대로 동작한다는 것은 보장된다.
어떠한 테스트 케이스의 answer 함수의 반환값이 어떠한 최선의 전략의 반환값으로도 불가능한 경우 를 받는다.
제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.
$N = 3$, $K = 2$인 경우를 생각해 보자. $1$번 관람객부터 $3$번 관람객까지 순서대로 $1$, $2$, $1$번 모자를 쓰고 있다고 가정하자.
그레이더가 첫 번째로 아래와 같은 answer 함수를 호출했다고 하자.
answer(3, 2, 1, [1, 2])함수 인자 중 $v$는 자신을 제외한 다른 사람들이 쓰고 있는 모자의 번호를 무작위로 제공함에 유의하라. 이제 위 함수는 $1$번 관람객이 전략에 따라 적을 숫자를 반환하면 된다.
뒤이어 그레이더가 두 번째, 세 번째로 아래와 같은 answer 함수를 호출했다고 하자.
answer(3, 2, 2, [1, 1]) answer(3, 2, 3, [2, 1])두 함수 호출은 각각 $2$번 관람객과 $3$번 관람객이 전략에 따라 적을 숫자를 반환하면 된다.
세 함수의 반환값이 각각 $1$, $2$, $1$이라면 관람객들이 입장료를 내지 않아도 된다. 반면 한 사람이라도 다르다면 관람객들은 입장료를 내야 한다. 여러분은 전략을 적절히 구성해 관람객들이 입장료를 내지 않아도 될 확률을 최대화하면 된다. 예제에서는 관람객의 순서대로 함수를 호출했지만, 실제 그레이더에서는 그렇지 않을 수 있음에 유의하라.
Sample grader는 첫 번째 줄에 테스트 케이스의 개수 $T$를 입력받는다. 그 이후 $T$회에 걸쳐 다음과 같은 정보를 입력받는다:
$e_1, \, e_2, \, \cdots, \, e_N$는 각 관람객들이 쓴 모자의 번호를 의미한다.
Sample grader는 각 테스트 케이스에 대해 다음을 출력한다.
Invalid Range를 출력한다.answer 함수의 반환값이 $1$ 이상 $K$ 이하가 아니라면 Wrong Answer를 출력한다.Invalid Range 또는 Wrong Answer를 출력할 시, Sample grader는 즉시 종료된다.
Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.
School > 경기과학고등학교 > 나는코더다 송년대회 > 나는코더다 2025 송년대회 E번
C++17