9657번: 돌 게임 3
상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.
www.acmicpc.net
dp로 해결할 수 있는 문제입니다.
상근이가 게임을 먼저 시작하고, 한 번에 가져갈 수 있는 돌의 갯수는 1개, 3개, 4개 입니다.
마지막에 돌은 가져간 사람은 승리하므로 dp[1] = true, dp[3] = true, dp[4] = true를 초기값으로 잡습니다.
그리고 dp[5]부터 dp[N]까지 반복문을 돌립니다.
여기서 i번째에서 돌을 가져갔을 때 남아있는 돌의 갯수에 따른 승패여부를 확인해야합니다.
돌을 1개 가져갔을 때 i - 1,
돌을 3개 가져갔을 때 i - 3,
돌을 4개 가져갔을 때 i - 4이므로
dp[i - 1], dp[i - 3], dp[i - 4]의 상황을 모두 체크해야합니다.
두 플레이어는 이기기 위해 최선을 다한다고 생각하고,
돌을 가져갔을 때 dp[i - 1], dp[i - 3], dp[i - 4] 모두가 true면 상대방이 무조건 이기는 경우이므로 false입니다.
반대로 dp[i - 1], dp[i - 3], dp[i - 4] 중 하나라도 false인 경우가 있으면 그 경우를 선택하면 무조건 이기므로 true입니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static boolean dp[] = new boolean[1001];
static int N;
static void func() {
dp[1] = true;
dp[3] = true;
dp[4] = true;
for (int i = 5; i <= N; i++) {
if (dp[i - 1] && dp[i - 3] && dp[i - 4])
dp[i] = false;
else
dp[i] = true;
}
}
static void print() {
if(dp[N])
System.out.println("SK");
else
System.out.println("CY");
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
}
public static void main(String[] args) throws Exception {
input();
func();
print();
}
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 5573 산책 (0) | 2021.02.04 |
|---|---|
| boj 17528 Two Machines (0) | 2021.01.28 |
| boj 2096 내려가기 (0) | 2021.01.22 |
| boj 1103 게임 (0) | 2021.01.22 |
| boj 12852 1로 만들기 2 (0) | 2021.01.22 |