https://www.acmicpc.net/problem/25427
25427번: DKSH를 찾아라
준혁이는 DKSH(단국대학교부속소프트웨어고등학교)에 다니는 학생이다. 어느 날, 준혁이는 길을 걷다가 $N$ 개의 알파벳 대문자가 써있는 종이를 발견했다. 평소에 자신이 DKSH에 다니는 학생이라
www.acmicpc.net
4개의 문자를 제외하고 모두 제거했을 때, 남은 문자열이 DKSH일 경우의 수를 구하는 문제입니다.
DKSH의 순서를 유지해야 하며, (a < b < c < d) 조건을 만족하는 (a, b, c, d) 쌍의 갯수를 구해야 합니다.
dp[idx][pos]: list의 idx번째 문자, DKSH 중 pos번쨰 문자를 확인할 때 "DKSH"를 만들 수 있는 경우의 수
우선 가장먼저 떠오른 방법이 재귀입니다.
pos == 4, 즉 DKSH를 모두 찾았다면 1을 리턴합니다.
DKSH를 모두 찾지 못했는데 list 내의 문자열을 모두 확인했다면 0을 리턴합니다.
모든 인덱스에 대해 해당 문자를 고르지 않고 idx + 1, pos번째 문자를 확인할 수 있습니다.
그리고 현재 idx번째 문자와 pos번째 문자가 일치하면 idx + 1, pos + 1번째 문자를 확인합니다.
두 가지의 경우를 모두 더해주시면 답이 되겠습니다.
여기까지 제가 생각했던 방법이고, 이 방법을 사용하지 않은 풀이도 존재합니다.
어떤 인덱스 idx를 기준으로 경우의 수를 조합하는 방법으로는
idx의 왼쪽에서 해당되는 문자의 갯수 * idx의 오른쪽에 해당되는 문자의 갯수로 구할 수 있습니다.
예시로 "YYYSSS"라는 문자열로 "YS"를 만들 수 있는 경우의 수는
왼쪽의 Y1 Y2 Y3 (3개) * 오른쪽의 S1 S2 S3 (3개) = 9로 구할 수 있습니다.
이를 변형해서 Y1 (S1 S2 S3) + Y2 (S1 S2 S3) + Y3 (S1 S2 S3)로도 구할 수 있으며, 이 문제는 이 방법을 이용합니다.
이 방법을 이용하여 해결할 수 있습니다.
찾은 문자에 대해서 왼쪽에 pos-1번 문자의 카운팅이 몇번 진행되었는지 확인만 해주면 됩니다.
'D'를 찾았다면 첫번째 문자이므로 d에 1을 더합니다.
'K'를 찾았다면 앞에 'D'가 카운팅 된 d를 k에 더해줍니다.
'S'를 찾았다면 앞에 'K'가 카운팅 된 k를 s에 더해줍니다.
'H'를 찾았다면 앞에 'S'가 카운팅 된 s를 h에 더해줍니다.
출력은 h를 해주시면 됩니다.
역시 두번째 방법이 O(N)으로 끝나기 때문에 속도가 더 빠름을 알 수 있습니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private final static int MAX = 100000;
private final static char pat[] = new char[]{'D', 'K', 'S', 'H'};
private static char[] list;
private static long dp[][] = new long[MAX][4];
private static int N;
private static long solve(int idx, int pos) {
if (pos == 4) return 1;
if (idx == N) return 0;
if (dp[idx][pos] != -1) return dp[idx][pos];
dp[idx][pos] = solve(idx + 1, pos);
if (list[idx] == pat[pos]) {
dp[idx][pos] += solve(idx + 1, pos + 1);
}
return dp[idx][pos];
}
private static void init() {
for (int i = 0; i < N; i++) {
Arrays.fill(dp[i], -1);
}
}
private static void func() {
init();
System.out.println(solve(0, 0));
}
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());
st = new StringTokenizer(br.readLine());
list = st.nextToken().toCharArray();
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static char[] list;
private static int N;
private static void func() {
long d = 0;
long k = 0;
long s = 0;
long h = 0;
for (int i = 0; i < N; i++) {
if (list[i] == 'D') d++;
else if (list[i] == 'K') k += d;
else if (list[i] == 'S') s += k;
else if (list[i] == 'H') h += s;
}
System.out.println(h);
}
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());
st = new StringTokenizer(br.readLine());
list = st.nextToken().toCharArray();
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 28018 시간이 겹칠까? (0) | 2023.08.08 |
|---|---|
| boj 12841 정보대 등산 (0) | 2023.07.31 |
| boj 25682 체스판 다시 칠하기 2 (0) | 2023.02.26 |
| boj 12996 Acka (0) | 2023.01.29 |
| boj 14450 Hoof, Paper, Scissors (Gold) (0) | 2022.12.30 |