[BOJ/21872] Deque Game, c++

🔗 링크

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

21872번: Deque Game

https://github.com/jokj624/PS/blob/master/20000-25000/21872.cpp

jokj624/PS

🤯 한줄 후기

한줄 후기 : 증명은 못하고. . . 

🤷 문제

👩‍💻 풀이

대회 스터디에서 연세대 신입생 대회 문제를 풀어보았는데, 그 중 한 문제이다. 

처음에 다른 친구가 풀고 생각보다 플래티넘 난이도 만큼의 구현은 아니라고 해서 도전. . . (플래티넘 맞는 거 같아)

 

문제가 길지만 읽어보면 간단한데 001블록을 갖고 있다 가정하자.

게임 룰은 블럭의 종류 중 아무거나 하나를 골라 주어진 층수에 맞는 블럭을 만들 때 까지 어디든 끼워 넣을 수 있다. 단, 이전에 나오지 않은 블럭 기둥만 가능하다. 예를 들어 블럭의 종류가 0, 1, 2, 3 이고, 층수가 4라면 

0101, 0201 등등 가능하지만 똑같은 블럭이 나오면 안된다. 

이런식으로 만들었을 때, 먼저 더이상 만들 수 있는 블럭이 없는 사람이 지는 게임이다.

 

처음에 보자마자 처음 주어진 고정 블럭의 길이가 다르다면 만들어야 하는 층수 L은 둘 다 같기 때문에 당연히 블럭 길이가 더 짧은 사람이 이긴다고 생각했다. 

블럭 길이가 같은 것이 관건이었는데 처음 구현한 코드에서는 블럭 길이가 같으면 가지고 있는 블럭 종류가 더 다양한 사람이 이긴다고 생각했다. 

 

사실 처음 주어진 블럭 길이가 둘 다 같다면 무조건 무승부이다. 

solved ac 난이도 기여에 있는 출제자 분의 말을 빌려오자면 

처음 주어진 스택이 000 일 때, 블럭 종류가 (0, 1, 2) 3개라 가정하자. 

000에 각 블럭을 넣었을 때 구분되는 블럭을 구분점이라 하면, 0 블럭은 구분점 0개, 1 블럭은 구분점 3개, 2 블럭은 구분점 3개로 총 7개이다.

마찬가지로 001 블럭을 보면, 0 블럭은 구분점 1개, 1 블럭은 구분점 2개, 2 블럭은 구분점 3개로 총 7개이다. 

이런식으로 접근하면 최종적으로 처음 받은 블럭 스택의 길이가 같으면 결과적으로 만들 수 있는 블럭 개수도 똑같아진다. 따라서 언제나 무승부가 된다.  

 

이 점을 파악하는 것이 이 문제를 푸는 것에 핵심인 것 같다.

한가지 또 주의해야 할 점은 블럭 종류가 1개일 때, 즉 K == 1 이어도 무조건 무승부이다!

둘 다 층 개수만큼 딱 한종류 블럭만 나오니까

💻 코드

//AC
//BOJ 21872 deque game
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main(){
	int G, K, L;
	cin >> G;
	scanf("%d %d", &K, &L); // K = 종류, L = 층 
	while(G--){
		int N, M;
		string y, s;
		scanf("%d", &N);	// N = 연돌 크기, M = 세순 크기
		cin >> y;
		scanf("%d", &M);
		cin >> s;
		if(N < M){
			if(K > 1) printf("Y\n"); // 가지고 있는 층이 더 낮으면 만들 수 있는 블록 많음
			else if(K == 1)	printf("YS\n");
		}
		else if(N > M){  
			if(K > 1)	printf("S\n");
			else if(K == 1)	printf("YS\n");
		}
		else if(N == M ){   // 가지고 있는 층이 같을 때
			printf("YS\n");
		}
	}
	return 0;
}