https://www.acmicpc.net/problem/20923
20923번: 숫자 할리갈리 게임
첫째 줄에는 도도와 수연이가 가지는 카드의 개수 $N$($ 1 \leq N \leq 30\,000$)과 게임 진행 횟수 $M$($ 1 \leq M \leq 2\,500\,000$)이 주어진다. 둘째 줄부터 $N$개의 줄에는 띄어쓰기로 구분하여 도도와 수연
www.acmicpc.net
🐢 접근방법
문제에서 나오는 덱(Deque) 자료구조를 사용하는 문제였다.
su와 do에게 주어진 카드들을 자신의 차례 때마다 하나씩 꺼내고 조건을 확인하고 (자신의 소유 개수가 0개인지, 나의 승리 조건 인지, 상대의 승리 조건인지) turn수를 증가시키고 종료시간일 경우 종료하도록 했다.
자신의 차례때 꺼낸 카드는 순서대로 쌓게 되는데 이때 승리 시 상대방이 냈던 쌓여있는 카드들을 역순으로 자신의 소유 카드 뒤에 추가하고, 자신이 냈던 쌓여있는 카드들도 역순으로 추가한다.
종료 시점은 승리 조건을 모두 확인 한 후에 종료 조건을 확인하도록 해야한다. turn은 한명 씩 번갈아 갈때마다 증가하고 조건 확인은 이와 상관없이 항상 체크해야한다.
🐢 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
import java.io.*;
import java.util.*;
public class 숫자할리갈리게임_20923 {
static int cards, playTime;
static Deque<Integer> doCards = new LinkedList<>();
static Deque<Integer> suCards = new LinkedList<>();
static Deque<Integer> doGround = new LinkedList<>();
static Deque<Integer> suGround = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
cards = Integer.parseInt(input[0]);
playTime = Integer.parseInt(input[1]);
for (int i = 0; i < cards; i++) {
input = br.readLine().split(" ");
doCards.push(Integer.parseInt(input[0]));
suCards.push(Integer.parseInt(input[1]));
}
int doCard, suCard;
int turn = 0;
while (true)
{
// do Turn
doCard = doCards.pop();
doGround.push(doCard);
if (doCards.isEmpty()) break;
if (doCard == 5) doWin();
else if (suGround.size() > 0 && doCard + suGround.peek() == 5) suWin();
if (++turn == playTime) break;
// su Turn
suCard = suCards.pop();
suGround.push(suCard);
if (suCards.isEmpty()) break;
if (suCard == 5) doWin();
else if (doGround.size() > 0 && suCard + doGround.peek() == 5) suWin();
if (++turn == playTime) break;
}
String s;
if (suCards.size() == doCards.size()) s = "dosu";
else s = suCards.size() > doCards.size() ? "su" : "do";
System.out.println(s);
}
private static void doWin() {
// 역순으로 자신의 카드에 추가 while (!suGround.isEmpty()) doCards.add(suGround.pollLast());
while (!doGround.isEmpty()) doCards.add(doGround.pollLast());
}
private static void suWin() {
// 역순으로 자신의 카드에 추가 while (!doGround.isEmpty()) suCards.add(doGround.pollLast());
while (!suGround.isEmpty()) suCards.add(suGround.pollLast());
}
}
|
cs |
|
|
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| (백준) 얼음 미로 - 20926 (0) | 2021.07.26 |
|---|---|
| (백준) 트리의 기둥과 가지 - 20924 (0) | 2021.07.25 |
| (백준) 음악프로그램 - 2623 (0) | 2021.07.23 |
| (백준) 보스몬스터 전리품 - 20005 (0) | 2021.07.22 |
| (백준) 가운데서 만나기 - 21940 (0) | 2021.07.22 |