[백준] 16877번: 핌버

🔈 문제

koosaga와 cubelover가 "핌버"를 하고 있다. 핌버는 님 게임에 규칙을 추가한 게임이다. 핌버는 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 핌버를 진행한다. 각 사람의 턴이 되면, 돌 더미 하나를 선택해 돌을 제거한다. 제거한 돌의 개수는 피보나치 수여야 한다. 전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다.  게임은 koosaga가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다.

 

📝입력

첫째 줄에 돌 더미의 개수 $N$ $(1 ≤ N ≤ 10^5)$이 주어진다. 둘째 줄에 각 돌 더미에 쌓여있는 돌의 개수 $P_i$ $(1 ≤ P_i ≤ 3×10^6)$가 주어진다.

 

 

📑출력

koosaga가 이기는 경우에는 "koosaga"를, cubelover가 이기는 경우에는 "cubelover"를 출력한다.

 

📚 문제 풀이

 

스프라그 그런디 문제였다. (나중에 시간이 된다면 스프라그 그런디 글도 써보는 걸로,,,)

 

손으로 쓱싹 20까지의 그런디 넘버를 계산했을 때, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5 이 반복되는 규칙이 보여 주기가 10인 그런디 넘버인줄 알았다. 하지만 이 규칙은 40 이상부터 깨졌다. 😅

 

결국 P의 최대값인 $3 * 10 ^ 6$ 까지의 모든 그런디 넘버를 찾고 xor 합을 취하는 문제였다. 이게 이 문제의 핵심인데, 그런디 넘버를 찾기 위해서 mex 함수를 돌릴 때 이것저것 해보면서 실행 속도를 줄이기 위한 과정을 남겨보고자 한다.

 

 

244ms

 

처음으로 정답 판정을 받은 코드이다.

 

	const FIBO: [usize; 32] = [
	1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,
	17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578,
	];
	fn mex(mut arr: Vec<bool>) -> u32 {
	for i in 0..arr.len() {
	if !arr[i] {
	return i as u32;
	}
	}
	arr.len() as u32
	}
	fn get_grundy() -> Vec<u32> {
	let n = 3_000_000;
	let mut grundy = vec![0u32; n + 1];
	grundy[1] = 1;
	for i in 2..=n {
	let mut visited: Vec<bool> = vec![false; 16];
	for j in FIBO {
	if i >= j {
	visited[grundy[i - j] as usize] = true;
	} else {
	break;
	}
	}
	grundy[i] = mex(visited);
	}
	grundy
	}

view raw fimbor1.rs hosted with ❤ by GitHub

 

주요 부분만 살펴보자면, 우선은 프로그램으로 돌려보았을 때 그런디 숫자가 최대 15까지라는 것을 파악했다. 평소에는 중복 제거를 위해 그런디 넘버를 저장할 때 HashSet을 사용했었는데, 여기서는 길이16짜리 bool 배열을 만들어서 확인하는 것이 더 효율적이라고 판단을 했다.

 

 

216 ms

첫 정답코드보다 30ms 가 줄었는데, 두 코드의 차이점은 전역 변수로 선언된 FIBO를 로컬 변수로 변경한 것이다. 그랬더니 작은 것 같으면서도 큰 30ms가 줄었다.

 

	fn mex(mut arr: Vec<bool>) -> u32 {
	for i in 0..arr.len() {
	if !arr[i] {
	return i as u32;
	}
	}
	arr.len() as u32
	}
	fn get_grundy() -> Vec<u32> {
	let n = 3_000_000;
	let mut grundy = vec![0u32; n + 1];
	grundy[1] = 1;
	let fibo = vec![
	1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,
	17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578];
	for i in 2..=n {
	let mut visited: Vec<bool> = vec![false; 16];
	for j in &fibo {
	if i >= *j {
	visited[grundy[i - *j] as usize] = true;
	} else {
	break;
	}
	}
	grundy[i] = mex(visited);
	}
	grundy
	}

view raw fimbor2.rs hosted with ❤ by GitHub

 

 

112 ms

 

거의 두배 가까이 줄였다. 이때는 배열에 저장하는 방법이 아닌, 비트마스킹을 사용해 mex 함수를 대체했다. 앞서 말했다시피 그런디 넘버가 최대 15를 넘지 않는다. 그렇기 때문에 굳이 16짜리의 bool 배열을 선언하는 것이 아닌 16비트의 숫자 하나로도 모든 것을 표현할 수 있다! (굉장히 쓰껄하지 아니한가)

 

비트마스킹을 간단하게 설명해보자면, bool 로 선언했을 때는 예를 들어 visited[3] 가 true 인지 false인지 판단을 해서 해당 값이 존재했는지 파악했다. 그런데 비트마스킹을 사용한다면 배열에 인덱스로 접근하는 것이 아니라 숫자에 특정 비트가 0인지 1인지 판단 하는 것이다.

 

	fn get_grundy() -> Vec<u32> {
	let n = 3_000_000;
	let mut grundy = vec![0u32; n + 1];
	grundy[1] = 1;
	let fibo = vec![
	1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,
	17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578];
	for i in 2..=n {
	let mut bit = 0i32;
	for j in &fibo {
	if i >= *j {
	bit |= 1 << grundy[i - *j];
	} else {
	break;
	}
	}
	grundy[i] = bit.trailing_ones();
	}
	grundy
	}

view raw fimbor3.rs hosted with ❤ by GitHub

 

이때는 따로 mex 함수를 만들지 않고, 러스트의 trailing_ones 함수를 사용하였다. trailing_ones 함수는 가장 오른쪽(least significant bit, LSB)부터 연속된 1의 개수를 반환하는 함수다.

 

 

68ms

 

비트마스킹 적용시킨 것에 멈추지 않고 한 발 더 나아가 낭비되고 있는 비트를 절약하였다.

 

여러 차례 언급하고 있는데 그런디 수는 최대 15이다. 그래서 굳이 u32 (32비트 음이 아닌 정수) 를 사용할 필요가 없고 u8(8비트 음이 아닌 정수)를 사용해도 충분했다. 그래서 사용하던 자료형을 변경해주었더니 시간이 50ms 정도 감소하였다.

 

	fn get_grundy() -> Vec<u8> {
	let n = 3_000_000;
	let mut grundy = vec![0u8; n + 1]; // grundy 배열을 u32 에서 u8로.
	grundy[1] = 1;
	let fibo = vec![
	1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,
	17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578];
	for i in 2..=n {
	let mut bit = 0i16; // 저장할 비트를 u32 에서 u16으로
	for j in &fibo {
	if i >= *j {
	bit |= 1 << grundy[i - *j];
	} else {
	break;
	}
	}
	grundy[i] = bit.trailing_ones() as u8;
	}
	grundy
	}

view raw fimbor4.rs hosted with ❤ by GitHub

 

 

 

💻 최종 코드

	use std::io::{read_to_string, stdin};
	fn main() {
	let stdin = read_to_string(stdin()).unwrap();
	let mut token = stdin.split_whitespace();
	let mut next = || token.next().unwrap();
	let n: usize = next().parse().unwrap();
	let nums: Vec<u32> = (0..n).map(|_| next().parse().unwrap()).collect();
	print!("{}", solve(n, nums));
	}
	fn solve(_n: usize, nums: Vec<u32>) -> String {
	let mut res =0 ;
	let nim = get_grundy();
	for num in nums {
	res ^= nim[num as usize];
	}
	if res != 0 {
	"koosaga".to_string()
	} else {
	"cubelover".to_string()
	}
	}
	fn get_grundy() -> Vec<u8> {
	let n = 3_000_000;
	let mut grundy = vec![0u8; n + 1];
	grundy[1] = 1;
	let fibo = vec![
	1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,
	17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578];
	for i in 2..=n {
	let mut bit = 0i16;
	for j in &fibo {
	if i >= *j {
	bit |= 1 << grundy[i - *j];
	} else {
	break;
	}
	}
	grundy[i] = bit.trailing_ones() as u8;
	}
	grundy
	}

view raw fimbor5.rs hosted with ❤ by GitHub

 

 

🍭 시행착오

 

 

맞힌 사람 전체에서도 일등을 먹고 있다.😎 (2025.3.30 기준)

 

 

 

🔗 문제링크 핌버