https://www.acmicpc.net/problem/14450
14450번: Hoof, Paper, Scissors (Gold)
You have probably heard of the game "Rock, Paper, Scissors". The cows like to play a similar game they call "Hoof, Paper, Scissors". The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each-other. They both count to three and then each s
www.acmicpc.net
가위바위보 마지막 문제입니다.
이 문제에서도 입력으로 상대방의 race가 주어지며, 베시는 같은 것만 여러번 연속으로 낼 수 있습니다.
Silver 문제와 다른 점은 K번까지 바꿀 수 있으며, K의 최대는 20입니다.
누적합으로는 해결할 수 없으며, dp와 재귀를 활용합니다.
dp[idx][cnt][race]: idx번째 게임에서 베시는 race를 cnt번 변경한 상태고, 현재 race를 낸 상태일 때 얻을 수 있는 최대 점수
3중 배열을 사용해야 하며, 첫 번째 게임에서 race를 낼 수 있는 경우 3가지를 모두 확인해야 합니다.
(race를 인덱스로 활용하고, 편의를 위해 입력에서 race를 숫자로 변경하였습니다.)
모든 경우에서 race를 변경하지 않고 연속으로 내는 경우를 구할 수 있고,
cnt < K인 경우에만 race를 변경하는 경우를 구하도록 합니다.
|
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private final static int MAX_N = 100001;
private final static int MAX_K = 21;
private static final int RACE_CNT = 3;
private static int list[] = new int[MAX_N];
private static int dp[][][] = new int[MAX_N][MAX_K][RACE_CNT];
private static int N, K;
private static void init() {
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= K; j++) {
Arrays.fill(dp[i][j], -1);
}
}
}
private static int getScore(int x, int y) {
if (x == 0 && y == 1) {
return 1;
} else if (x == 1 && y == 2) {
return 1;
} else if (x == 2 && y == 0) {
return 1;
} else {
return 0;
}
}
private static int dfs(int idx, int cnt, int race) {
if (idx > N) {
return 0;
}
if (dp[idx][cnt][race] != -1) {
return dp[idx][cnt][race];
}
dp[idx][cnt][race] = dfs(idx + 1, cnt, race) + getScore(race, list[idx]);
if (cnt < K) {
dp[idx][cnt][race] = Math.max(dp[idx][cnt][race], dfs(idx + 1, cnt + 1, (race + 1) % RACE_CNT) + getScore(race, list[idx]));
dp[idx][cnt][race] = Math.max(dp[idx][cnt][race], dfs(idx + 1, cnt + 1, (race + 2) % RACE_CNT) + getScore(race, list[idx]));
}
return dp[idx][cnt][race];
}
private static void func() {
init();
System.out.println(Math.max(dfs(1, 0, 0), Math.max(dfs(1, 0, 1), dfs(1, 0, 2))));
}
private static int getRace(char x) {
if (x == 'H') {
return 0;
} else if (x == 'S') {
return 1;
} else {
return 2;
}
}
private static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = getRace(st.nextToken().charAt(0));
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 25682 체스판 다시 칠하기 2 (0) | 2023.02.26 |
|---|---|
| boj 12996 Acka (0) | 2023.01.29 |
| boj 14453 Hoof, Paper, Scissors (Silver) (0) | 2022.12.30 |
| boj 2281 데스노트 (0) | 2022.10.08 |
| boj 2015 수들의 합 4 (0) | 2022.08.12 |