boj 25427 DKSH를 찾아라

https://www.acmicpc.net/problem/25427

25427번: DKSH를 찾아라

 

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)으로 끝나기 때문에 속도가 더 빠름을 알 수 있습니다.

 

 

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();
    }
}
 

 

 

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();
    }
}