[BOJ 백준] 25427번 : DKSH를 찾아라 (C++)

[BOJ 백준] 25427번 : DKSH를 찾아라 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드
• 04. 마무리

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. 뒤에서부터 검사를 진행해, 각 글자마다 'D', 'K', 'S', 'H'인지 확인하고 일치한다면, 아래와 같이 진행

 

1) 현재 글자가 H인 경우, 현재 위치에서 마지막까지 H의 개수

2) 현재 글자가 S인 경우, 현재 위치에서 마지막까지 SH를 구성하는 개수 (기존 SH개수 + 현재 H 개수)

3) 현재 글자가 K인 경우, 현재 위치에서 마지막까지 KSH를 구성하는 개수 (기존 KSH개수 + 현재 SH 개수)

4) 현재 글자가 D인 경우, 현재 위치에서 마지막까지 DKSH를 구성하는 개수 (기존 DKSH개수 + 현재 KSH 개수)

 

2. 검사를 모두 종료하고 난 후, DKSH 개수를 반환

 

과정

위 문제는 누적합으로 해결할 수 있는 문제입니다.

 

먼저, 뒤에서부터 검사를 진행합니다.

현재 위치에서 각 경우를 기록하기 위해 DKSH, KSH, SH, H에 대한 변수를 선언합니다.

 

그리고 간단한 예시를 통해서 위에 적힌 과정을 자세히 살펴보겠습니다.

 

입력값을 DKSHSH로 주어진다고 가정하겠습니다.

글자 D, K, S, H를 제외하고는 다른 글자는 필요 없습니다.

그래서, 실제로 검사를 할 때, 다른 글자는 바로 무시하셔도 됩니다. 

 

뒤에서부터 검사를 진행합니다.

현재 글자는 H이므로, H의 개수를 1개 증가시킵니다.

 

글자 S를 발견했을 때는 현재 위치를 기준으로 뒤에 H가 몇 개 있는지 확인하면, 현재 글자(S)와 H를 조합한 경우가 됩니다.

따라서, H의 개수인 1을 더합니다.

 

다시 글자 H를 발견했으므로, H의 개수를 1 증가시킵니다.

 

글자 S를 발견했습니다.

현재 글자(S)를 기준으로 SH를 만들 수 있는 경우는 위치 3과 위치 5에 있는 H와 조합하는 경우입니다.

따라서, 현재 H의 개수를 더해, SH의 개수는 총 3개가 됩니다.

 

글자 K와 글자 D를 발견했을 때도 글자 S를 발견했을 때처럼 동작합니다.

글자 K를 발견했을 때, 현재 글자(K)를 기준으로 뒤에 SH가 오는 경우를 더하면 됩니다.

글자 D를 발견했을 때, 현재 글자(D)를 기준으로 뒤에 KSH가 오는 경우를 더하면 됩니다.

 

따라서, 위의 경우에는 DKSH 경우는 총 3가지입니다.

 

 

다른 예시로 DKSHDKSHDKSH에 대한 경우를 살펴보겠습니다.

위 경우에는 결괏값이 15입니다.

 

 

---

03. 정답 코드

// 골드 5 - 25427번 : DKSH를 찾아라
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// 그냥 DKSH 글자만 남기기
// 남겼을 때, DKSH가 되는 경우의 수
// 즉, a번째 문자 D, b번째 문자 K, c번째 문자 S, d번째 문자 H
// a < b < c < d를 만족하는 경우의 수 구하기

// 글자 길이 -> N (1~100'000)
// 둘째 줄 -> 문자열

// 1번
// 11
// DABKCDSEFHH

// 일단 DKSH만 남기기

// DKSHH -> 2가지 경우

// DDKSHH -> 4가지 경우
// DDKDKSHH -> 10가지 경우

// DKSH
// S -> 뒤에 H 개수 
// K -> 뒤에 SH 개수
// D -> 뒤에 KSH 개수 

// H -> 1개 추가
// S -> 기존 SH 개수 + 현재 H 경우
// K -> 기존 KSH 개수 + 현재 SH 경우
// D -> 기존 DKSH 개수 + 현재 KSH 경우

// DKSHDKSHDKSH
// (좌표, 개수)
// D : (0,15)(4,5)(8,1)
// K : (1,10)(5,4)(9,1)
// S : (2,6)(6,3)(10,1)
// H : (3,3)(7,2)(11,1)

// int 범위 벗어남
using ll = long long;

ll simulate(const string& input)
{
    // 뒤에서 검사
    ll h_count = 0;
    ll sh_count = 0;
    ll ksh_count = 0;
    ll dksh_count = 0;

    for(int i = input.length()-1; i >= 0; i--)
    {
        // H 개수 증가
        if(input[i] == 'H')
            h_count++;

        // 기존 SH 경우 + 현재 H 경우
        else if(input[i] == 'S')
            sh_count += h_count;

        // 기존 KSH 경우 + 현재 SH 경우
        else if(input[i] == 'K')
            ksh_count += sh_count;

        // 기존 DKSH 경우 + 현재 KSH 경우
        else if(input[i] == 'D')
            dksh_count += ksh_count;
    }

    return dksh_count;
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 글자 길이 N
    int N;
    cin >> N;

    // 문자열 입력
    string input;
    cin >> input;

    cout << simulate(input) << "\n";
}

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!