백준 21872 Deque Game C++

문제

21세기 최고의 게임! 연돌이와 세순이들의 극찬을 받아낸 게임! 세계를 매혹한 게임! 바로 Deque Game입니다.

Deque Game은 두 사람이 각자 주어진 블록을 이용해 L$L$층을 더 다양한 방식으로 쌓을 수 있는 사람이 승리하는 게임이다. Deque Game의 자세한 규칙은 다음과 같다.

1. 총 $K$종류의 블록이 있고, 연돌이와 세순이는 원하는 만큼 블록을 가져다 사용할 수 있다. 블록에는 $0$이상 $K$미만의 정수가 적혀있으며, 블록을 여러 개 쌓아서 스택을 만들 수 있다.0
2. K
3. K
4. 게임 시작 전, 연돌이와 세순이는 각자 $N$, $M$층의 스택을 무수히 많이 받는다. 연돌이가 받는 모든 스택은 동일하다. 세순이가 받는 모든 스택도 동일하다.M
5. N
6. 연돌이와 세순이는 매초 본인이 받은 스택 중 하나를 고른다. 그리고 임의의 블록을 끼워 넣는다. 스택의 가장 아래나, 가장 위, 심지어 중간에도 끼워 넣을 수 있다. 이미 $L$층이 쌓인 스택은 고르지 않는다.
7. L
8. 충분히 많은 시간이 흐르면, 더 이상 새로운 방법으로 $L$층의 스택을 만들 수 없을 것이다. 이때, 둘 중 더 많은 방식으로 $L$층의 스택을 완성한 사람이 승리한다. 만약 $L$층의 스택을 완성하는 방식의 수가 같다면 승부가 나지 않는다.L
9. L
10. L

예를 들어 연돌이는 2$2$층짜리 00$00$스택을 무수히 많이 받고, 세순이는 2$2$층짜리 22$22$스택을 무수히 많이 받았다. 총 3$3$종류의 블록을 이용해서 3$3$층 스택을 쌓는 방법의 수는 7$7$가지로 같다. 이 Deque Game은 승부가 나지 않는다.

https://upload.acmicpc.net/d1f28ae8-b7b2-40f2-8010-c2f950f2e504/

https://upload.acmicpc.net/c1a846ea-0684-4879-b6ef-bd22256acf80/

곧 밤 10시가 되기 때문에 마호가니 아르바이트생 선렬이는 문을 닫을 준비를 해야 한다. 하지만 이 순간에도 연돌이들과 세순이들이 Deque Game을 열심히 하고 있다. 선렬이는 매 게임판을 돌아다니며 Deque Game의 승자를 알려주기로 했다. 재빨리 Deque Game의 승자를 알려주고 게임판을 접지 않으면, 10시에 문을 닫지 못하고 벌금을 내야 할 것이다!

입력

첫 번째 줄에 마호가니에서 연돌이와 세순이가 진행하는 Deque Game의 수 G$G$가 주어진다. (1≤G≤3000$1 \leq G \leq 3\,000$)

두 번째 줄에 블록 종류의 개수를 나타내는 K$K$와 쌓아야 하는 스택의 층수를 나타내는 L$L$이 주어진다. (1≤K≤10$1 \leq K \leq 10$, 1≤L≤2000$1 \leq L \leq 2\,000$)

세 번째 줄부터 G$G$개의 Deque Game에 대한 정보가 다음과 주어진다.

• 연돌이가 받은 스택의 크기를 나타내는 정수 $N$이 주어진다. ($1 \leq N \leq L$)1≤N≤L
• N
• 연돌이가 받은 스택을 나타내는 문자열 $S$가 주어진다. 문자열 $S$의 길이는 $N$이고, 스택을 나타내는 문자열은 최하단 블록부터 주어진다.S
• N
• S
• 세순이가 받은 스택의 크기를 나타내는 정수 $M$이 주어진다. ($1 \leq M \leq L$)1≤M≤L
• M
• 세순이가 받은 스택을 나타내는 문자열 $T$가 주어진다. 문자열 $T$의 길이는 $M$이고, 스택을 나타내는 문자열은 최하단 블록부터 주어진다.T
• M
• T

연돌이와 세순이가 받은 스택의 블록에는 0$0$이상 K$K$미만의 정수가 적혀있다.

출력

G$G$개의 줄에 Deque Game의 승자를 출력한다.

연돌이가 승리하면 Y를, 세순이가 승리하면 S를 출력한다. 만약 승부가 나지 않는다면 YS를 출력한다.

예제 입력 1

1
3 3
2
00
2
22

예제 출력 1

YS

연돌이는 7$7$가지 방식으로 3$3$층 스택을 만들 수 있고, 세순이는 7$7$가지 방식으로 3$3$층 스택을 만들 수 있다.

• 연돌이 : $000, 001, 010, 100, 002, 020, 200$
• 000,001,010,100,002,020,200
• 세순이 : $220, 202, 022, 221, 212, 122, 222$
• 220,202,022,221,212,122,222

예제 입력 2

2
3 3
1
0
3
012
3
012
2
22

예제 출력 2

Y
S

게임 1

연돌이는 19$19$가지 방식으로 3$3$층 스택을 만들 수 있고, 세순이는 1$1$가지 방식으로 3$3$층 스택을 만들 수 있다.

따라서 연돌이가 Deque Game에서 승리한다.

• 연돌이 : $000, 001, 002, 010, 011, 012, 020, 021, 022, 100, 101, 102, 110, 120, 200, 201, 202, 210, 220$
• 000,001,002,010,011,012,020,021,022,100,101,102,110,120,200,201,202,210,220
• 세순이 : $012$
• 012

게임 2

연돌이는 1$1$가지 방식으로 3$3$층 스택을 만들 수 있고, 세순이는 7$7$가지 방식으로 3$3$층 스택을 만들 수 있다.

따라서 세순이가 Deque Game에서 승리한다.

• 연돌이 : $012$
• 012
• 세순이 : $022, 122, 222, 202, 220, 212, 221$
• 022,122,222,202,220,212,221

출처

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

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

알고리즘 분류

• 수학
• 애드 혹
• 조합론

내 풀이

#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;
}