c언어 25427번 DKSH를 찾아라 (백준)

#include <stdio.h>

int main(void)
{
	long long n, d=0, dk=0, dks=0, dksh=0;
	
	scanf("%lld", &n);
	char arr[n+1];
	scanf("%s", arr);
	
	for(int i=0; i<n; i++) {
		if(arr[i] == 'D') d++;
		else if(arr[i] == 'K') dk+=d;
		else if(arr[i] == 'S') dks += dk;
		else if(arr[i] == 'H') dksh += dks;
	}
	printf("%lld", dksh);
}

풀이 : 누적 합

 

D, K, S, H 을 봅시다.

 

D가 나올때 마다 d을 증가시켜주다가

K가 나오게 되면 만들수 있는 DK의 개수는 d와 같습니다.

S가 나오게 되면 만들수 있는 DKS의 개수는 dk와 같습니다.

H가 나오게 되면 만들수 있는 DKSH의 개수는 dks와 같습니다.

 

이를 이용해서, D, K, S, H가 나올 때마다 이와 관련된 변수들의 값을 변경해주면 됩니다.

 

마지막으로 DKSH의 개수인 dksh을 출력합니다.

 

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

25427번: DKSH를 찾아라