(알고리즘) 백준 25427 java 자바

원종식·2022년 8월 19일

문제

백준 25427 DKSH를 찾아라 : https://www.acmicpc.net/problem/25427

준혁이는 DKSH(단국대학교부속소프트웨어고등학교)에 다니는 학생이다. 어느 날, 준혁이는 길을 걷다가 $N$ 개의 알파벳 대문자가 써있는 종이를 발견했다. 평소에 자신이 DKSH에 다니는 학생이라는 것을 자랑스러워하던 준혁이는 이 종이에서 네 개의 문자를 골라서 그 문자들을 제외한 나머지 문자를 전부 지웠을 때 "DKSH"가 되도록 하려고 한다. 준혁이는 이렇게 네 개의 문자를 고르는 방법의 수를 세어 보기로 했다. 하지만 영어울렁증이 있는 준혁이는 금방 포기해버리고 말았다. 준혁이를 도와 네 개의 문자를 골라 나머지 문자를 전부 지웠을 때 "DKSH"가 되는 경우의 수를 세어 주자.(큰 따옴표 제외) 정확히는, 문자열에서 $a$ 번째 문자가 'D', $b$ 번째 문자가 'K', $c$ 번째 문자가 'S', $d$ 번째 문자가 'H'이고 $a<b<c<d$ 인 순서쌍 ( $a, b, c, d$ )의 갯수를 찾자.

입력

첫째 줄에 $N$ 이 주어진다. $(1≤N≤100,000)$
둘째 줄에 길이 $N$ 의 문자열 $S$ 가 주어진다. ( $S$ 는 알파벳 대문자로만 이루어져 있다.)

출력

첫째 줄에 문제에서 설명한 순서쌍 ( $a, b, c, d$ )의 갯수를 출력한다.

서브태스크

예제 입력 1

11
DABKCDSEFHH

예제 출력 1

풀이

해당 문제는 dp로 풀었다
DKSH의 순서대로 문자열을 만들 수 있는 개수이다.
문자열에서 H를 만났을때 해당 위치에서 가능한 DKSH를 선택하는 경우는
직전까지 DKSH를 만들었던 개수 + 직전까지 DKS를 만들 수 있는 경우의 수이다.
이를 DK,DKS에도 적용하면
다음과 같은 공식이 만들어 진다.
d는 지금까지 D를 만들 수 있는 경우의 수는
만약 지금이 D면 이전까지 D를 만들 수 있는 경우의 수 +1
DK는
이전까지의 DK+ 이전까지 D를 만들 수 있는 경우의 수
DKS는 이전까지의 DKS+ 이전까지 DK이다
코드를 통해 보자

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class BOJ25427 {
    public static void main(String args[]) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        String get=br.readLine();
        long d=0;
        long k=0;
        long s=0;
        long h=0;

        if(get.charAt(0)=='D'){
            d=1;
        }

        for(int i=1;i<n;i++){
            if(get.charAt(i)=='D'){
                d++;
                continue;
            }
            if(get.charAt(i)=='K'){
                k+=d;
                continue;
            }
            if(get.charAt(i)=='S'){
                s+=k;
                continue;
            }
            if(get.charAt(i)=='H'){
                h+=s;
                continue;
			}
        }
        System.out.println(h);
    }
}