[BOJ] 백준 21874 - 모자 게임 (2021 연세대학교 신입생 프로그래밍 경진대회)

문제 링크

https://www.acmicpc.net/problem/21874

21874번: 모자 게임

 

풀이

생각을 좀 해보다, 첫 사람이 전체에 대한 정보를 모두 줘야 한다고 판단했습니다.

 

처음에 모든 모자의 합을 알려주고, 각 사람은 내가 볼 수 있는 수와 지금까지 나왔던 수를 합에서 빼면 자기 모자의 수를 알 수 있습니다.

근데 수의 범위가 0 ~ 63입니다.

사람처럼 생각하면 덧셈, 뺄셈이 이상적이지만, 컴퓨터는 xor을 쉽게 할 수 있습니다.

처음에 모든 모자의 xor 값을 알려주고, 각 사람마다 나머지 모자의 수를 xor 해주도록 합시다.

 

사실 조금 더 사람답게 생각하기를 포기하면 코드가 더 간결해집니다.

첫 사람이 알려준다는 개념 없이, 앞, 뒤 구분 없이, 그냥 매턴 똑같이 F의 모든 값, B의 모든 값을 xor 해주면 같은 답이 나옵니다.

어찌 됐든 논리는 같습니다.

 

정답 코드

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

int n;
void init(int N){
    n = N;
}

int call(vector<int> F, vector<int> B, int num){
    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;
}

// ================================================== //

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

void init(int N){}

int call(vector<int> F, vector<int> B, int num){
    int ret = 0;
    for(int i: F) ret ^= i;
    for(int i: B) ret ^= i;
    
    return ret;
}