[BOJ/백준] 25427 - DKSH를 찾아라

25427번: DKSH를 찾아라

---

D, DK, DKS → Dynamic Programming

---

---

• 제목

DKSH를 찾아라

---

• 조건

시간 제한 : 1 초

메모리 제한 : 512 MB 

---

• 문제

준혁이는 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	예제 출력1
11 DABKCDSEFHH	2

---

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define endl '\n'
#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define SIZE 100000
int main() {
    fastio;
    string str;
    long long D[SIZE] = {0, };
	long long DK[SIZE] = {0, };
	long long DKS[SIZE] = {0, }, sz;
	long long cnt = 0;
    cin >> sz >> str;
    // DABKCDSEFHH
    for(int n = 0 ; n < sz ; n++){
		if(n != 0){
			D[n] = D[n - 1];
			DK[n] = DK[n - 1];
			DKS[n] = DKS[n - 1];
		}
    	if(str[n] == 'D' || str[n] == 'K' || str[n] == 'S' || str[n] == 'H'){
    		switch(str[n]){
    			case 'D':{
    				if(n == 0) D[n] = 1;
    				else D[n] = D[n - 1] + 1;
					break;
				}
    			case 'K':{
    				if(n != 0) DK[n] = D[n - 1] + DK[n - 1]; 
					break;
				}
    			case 'S':{
    				if(n != 0) DKS[n] = DK[n - 1] + DKS[n - 1];
					break;
				}
    			case 'H':{
    				if(n != 0) cnt += DKS[n - 1];
					break;
				}
			}
		}
	}	
	cout << cnt << endl;
	return 0;
}