백준 21874 모자 게임 C++

문제

https://upload.acmicpc.net/49ef4c39-5833-4ed7-8e40-8a883161e659/-/preview/

CS-House에서는 매주 목요일에 연세대학교 컴퓨터과학과에 대한 여러 이야기를 팟캐스트 형식으로 다룬다. 2021년 3월 18일에 진행한 CS-House에서는 ICPC World Final에 진출한 윤인섭 선배가 게스트로 나와서 알고리즘 및 Competitive Programming에 대해서 이야기를 했다. 이야기 도중에 시청자들과 함께 재미있는 문제들을 풀어보는 시간을 가졌는데, 그 문제 중 하나를 변형해서 연세대학교 신입생 프로그래밍 경진대회에 내기로 했다. 다음과 같은 문제를 생각해보자.

https://upload.acmicpc.net/6d1c64a8-c896-46d6-8d2d-300ed8efa697/-/preview/

그림과 같이 N$N$명의 사람이 앞을 보고 일렬로 서있다. 각 사람은 맨 뒷사람을 제외하고 0$0$ 이상 63$63$ 이하의 정수가 적힌 모자를 쓰고 있다.

https://upload.acmicpc.net/6aa76f61-ae82-4fb4-87fe-715b515a0088/-/preview/

각 사람은 자신보다 앞에 있는 사람의 모자에 적힌 수를 모두 볼 수 있지만, 자신을 포함해서 뒤에 있는 사람의 모자에 적힌 수는 볼 수 없다.

https://upload.acmicpc.net/16cbd0ee-12c7-439e-97e3-40f48af48263/-/preview/

https://upload.acmicpc.net/6b3f821c-cf4f-40e1-8619-aa06ca586aa1/-/preview/

게임이 시작되면 맨 뒷 사람부터 순서대로 0$0$ 이상 63$63$ 이하의 정수 중 하나를 말한다.

게임을 시작하기 전 N$N$명의 사람들이 모여 작전을 세우려고 한다. 자신이 말한 수와 자신의 모자에 적힌 수가 동일한 사람이 최대한 많아지도록 작전을 세워보자.

구현

이 문제를 풀기 위해서는 hat.cpp 파일을 제출해야 한다. hat.cpp 파일에 포함되어야 하는 함수는 다음과 같다..

void init(int N);

• 프로그램이 실행된 직후, 한 번만 호출된다. N은 일렬로 서있는 사람의 수를 의미한다.

int call(vector<int> F, vector<int> B, int num);

• 앞에서부터 (num+1)번째에 서있는 사람이 말해야 하는 수를 return한다. num은 $0$ 이상 $N-1$ 이하의 정수다.N−1
• 0
• F는 앞에 있는 사람들이 쓴 모자의 수를 저장한 길이 $N$의 정수 배열이다. F[i]에는 i+1번째 사람이 쓴 모자의 수가 저장되어 있다. 만약 num+1번째 사람이 i+1번째 사람이 쓴 모자의 수를 볼 수 없다면 해당 배열 값은 $0$이다.0
• N
• B는 뒤에 있는 사람들이 말한 수를 저장한 길이 $N$의 정수 배열이다. B[i]에는 i+1번째 사람이 말한 수가 저장되어 있다. 만약 num+1번째 사람이 말하기 전에 i+1번째 사람이 말하는 차례가 오지 않았다면 해당 배열 값은 $0$이다.0
• N
• 각 게임마다 call은 총 $N$번 호출된다. call이 호출될 때 마다 num에는 $N-1$부터 $0$까지 수가 순서대로 들어간다.N−1
• 0
• N

총 T$T$번의 모자 게임이 동시에 진행되며, 각 게임별로 N−1$N-1$명이 자신이 쓴 모자에 적힌 수와 동일한 수를 말해야 **맞았습니다!!**를 받을 수 있다. Grader가 실행 도중 틀렸습니다라고 판정한 경우, 그 즉시 프로그램이 종료된다.

제한

• $1 \le N \le 10$
• 1≤N≤10
• $1 \le T \le 200\,000$
• 1≤T≤200000

첨부

• sample_grader.cpp
• hat.cpp
• hat.h

출처

University > 연세대학교 > 2021 연세대학교 신입생 프로그래밍 경진대회 I번

• 문제를 검수한 사람: ggoh, Juno, Picasso, pinebananais, QuqqU, sogangcse, standingbell
• 문제를 만든 사람: lky7674

알고리즘 분류

• 수학
• 애드 혹

제출할 수 있는 언어

C++17, C++11, C++14, C++20

채점 및 기타 정보

• 예제는 채점하지 않는다.

내 풀이

#include "hat.h"
#include <vector>
using namespace std;

int n;

void init(int N)
{
	// Do Something...
    n = N;
}

int call(vector<int> F, vector<int> B, int num)
{
	// Do Something...
	if (num == n - 1) {
		int ret = 0;
		for (int i : F) {
			ret ^= i;
		}
		return ret;
	}
	int ret = B[n - 1];
	for (int i = 0; i < num; i++) {
		ret ^= F[i];
	}
	for (int i = num + 1; i < n - 1; i++) {
		ret ^= B[i];
	}

	return ret;
}