Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 다이나믹 프로그래밍으로 인접한 1이 K번 나타나는 이진 문자열 개수 계산하기

문제 개요

정수 N과 K가 주어집니다. 0과 1로만 구성된 길이 N의 이진 문자열 중에서, 인접한 1이 정확히 K번 나타나는 문자열의 개수를 구하는 것이 목표입니다.

예를 들어 N=3, K=2라면, 길이 3의 모든 이진 문자열 중에서 인접한 1이 두 번 나타나는 문자열의 개수를 세어야 합니다.

  • 111 — 인접한 1이 두 번 나타납니다 (K번).
  • 011, 110 — 인접한 1이 한 번만 나타납니다.

해결 아이디어: 다이나믹 프로그래밍(DP)

이 문제는 이전에 계산한 결과값을 저장해 두는 방식, 즉 다이나믹 프로그래밍으로 효율적으로 해결할 수 있습니다.

3차원 배열 count[x][y][z]를 사용합니다. 여기서 x는 문자열의 길이(N), y는 인접한 1의 개수(K), z는 문자열의 마지막 자릿수(0 또는 1)를 의미합니다.

기저 조건

N=1일 때 가능한 문자열은 "0"과 "1"뿐이며, 이 경우 인접한 1의 개수는 항상 0입니다. 따라서 어떤 K에 대해서도 N=1이면 개수는 0입니다.

count[1][K][0] = count[1][K][1] = 0

마지막 자릿수가 0인 경우

길이 N-1이면서 인접한 1이 K개인 모든 문자열 뒤에 0을 붙이면 길이 N의 새로운 문자열이 됩니다. 끝에 0을 추가해도 인접한 1의 개수는 변하지 않습니다.

count[N][K][0] = count[N-1][K][0] + count[N-1][K][1]

마지막 자릿수가 1인 경우

두 가지 경우를 고려해야 합니다.

  • 길이 N-1이고 0으로 끝나며 인접한 1이 K개인 문자열 + 마지막 1 → count[N-1][K][0]
  • 길이 N-1이고 1로 끝나며 인접한 1이 K-1개인 문자열 + 마지막 1 → count[N-1][K-1][1]

count[N][K][1] = count[N-1][K][0] + count[N-1][K-1][1]

따라서 조건을 만족하는 전체 문자열의 개수는 다음과 같습니다.

정답 = count[N][K][0] + count[N][K][1]

입력 / 출력 예제

예제 1

N=4, K=2

출력:

Count of strings: 2

설명 — 길이 4의 문자열 중에서 인접한 1이 정확히 두 번 나타나는 것은 1110과 0111뿐입니다.

1110 - "11 10", 그리고 "1 11 0" (어느 위치의 인접한 1이 세어지는지 보여주기 위해 구분)
0111 - "0 11 1", 그리고 "01 11". K=2, 인접한 1의 등장 횟수 = 2회

예제 2

N=3, K=1

출력:

Count of strings: 2

설명 — 길이 3의 문자열 중에서 인접한 1이 한 번만 나타나는 것은 110과 011입니다. 참고로 111에서는 인접한 1이 두 번 나타나므로 제외됩니다.

알고리즘 접근 방법

  1. 정수 N과 K는 각각 문자열의 길이와 인접한 1이 나타나야 하는 횟수를 저장합니다.
  2. 함수 stringcount(int n, int k)는 n과 k를 매개변수로 받아 인접한 1이 K번 나타나는 문자열의 개수를 반환합니다.
  3. 배열 count[i][j][0/1]은 길이 i이고 인접한 1이 j개이며 0 또는 1로 끝나는 문자열의 개수를 저장합니다.
  4. 초기 조건은 count[1][0][0] = 1;, count[1][0][1] = 1; 입니다.
  5. 길이 2(i=2)부터 n까지 반복하면서, 각 j(0 ≤ j ≤ k)에 대해 이전 결과를 바탕으로 count[i][j][0]과 count[i][j][1]을 갱신합니다.
  6. j-1 ≥ 0이면(인접한 1의 개수가 1보다 클 때) 1로 끝나는 문자열의 개수를 count[i][j][1] += count[i-1][j-1][1]로 갱신합니다.
  7. 마지막에 count[n][k][0]과 count[n][k][1]을 더하여 결과를 저장합니다.
  8. 계산된 결과값을 원하는 개수로 반환합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
int stringcount(int n, int k){
    // 길이=n이고 인접한 1의 개수=k인 문자열의 개수
    int count[n + 1][k + 1][2]={0};
    // count[n][k][0] -- 길이=n, 인접한 1의 개수=k, 마지막 문자가 0인 문자열
    // count[n][k][1] -- 길이=n, 인접한 1의 개수=k, 마지막 문자가 1인 문자열
    // n = 1이고 k = 0인 초기 조건
    count[1][0][0] = 1;
    count[1][0][1] = 1;
    for (int i = 2; i <= n; i++) {
        // 인접한 1의 개수는 i-1을 초과할 수 없음
        for (int j = 0; j <= k; j++) {
            count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1];
            count[i][j][1] = count[i - 1][j][0];
        if (j - 1 >= 0)
            count[i][j][1] = count[i][j][1] + count[i - 1][j - 1][1];
        }
    }
    int result = count[n][k][0] + count[n][k][1];
    return result;
}
int main(){
    int N = 6, K = 3;
    cout << "Strings of length 6 and 3 adjacent 1's in each :" << stringcount(N,K);
    return 0;
}

실행 결과

Strings of length 6 and 3 adjacent 1's in each :7

마무리

이처럼 3차원 DP 배열을 활용하면 길이 N의 이진 문자열 중에서 인접한 1이 정확히 K번 나타나는 문자열의 개수를 O(N×K) 시간 복잡도로 효율적으로 계산할 수 있습니다. 완전 탐색으로는 2^N개의 문자열을 일일이 확인해야 하지만, DP를 사용하면 이전 상태의 결과를 재활용하므로 N이 커져도 빠르게 답을 구할 수 있다는 점이 이 기법의 가장 큰 장점입니다.