C++로 연속된 요소의 값이 서로 다른 배열 개수 구하기

문제 정의

세 개의 변수 size(배열의 크기), max_val(요소가 가질 수 있는 최댓값), last_element(마지막 요소)가 입력으로 주어졌을 때, 다음 조건을 모두 만족하는 서로 다른 배열의 개수를 구하는 것이 목표입니다.

배열은 정확히 size개의 요소로 구성됩니다.
모든 요소는 1부터 max_val 사이의 값이어야 합니다.
첫 번째 요소는 항상 1입니다.
마지막 요소는 항상 last_element입니다.
연속된 두 요소의 값은 서로 달라야 합니다.

예시로 이해하기

예시 1

입력: size = 5, max_val = 3, last_element = 3

출력: 연속된 요소의 값이 서로 다른 배열의 개수: 5

설명: 만들 수 있는 배열은 다음과 같습니다.

[1, 2, 3, 1, 3], [1, 2, 3, 2, 3], [1, 2, 1, 2, 3], [1, 3, 1, 2, 3], [1, 3, 2, 1, 3]

예시 2

입력: size = 3, max_val = 2, last_element = 2

출력: 0

설명: 배열의 형태가 [1, _, 2]가 되어야 하는데, 가운데 요소에 넣을 수 있는 값은 1 또는 2뿐입니다. 어떤 값을 넣더라도 양옆 요소 중 하나와 같아져 연속된 요소가 서로 달라야 한다는 조건을 위반하므로, 가능한 배열은 하나도 없습니다.

풀이 접근 방식

이 문제는 동적 계획법(DP)과 조합론적 사고를 결합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

첫 번째 요소와 마지막 요소는 각각 1과 last_element로 고정되어 있으므로, 실제로 채워야 할 자리는 size - 2개뿐입니다.
각 길이별로 배열을 채우는 방법의 수를 arr 배열에 누적하여 저장합니다. 초기값은 arr[0] = 0, arr[1] = 1입니다.
i번째 자리를 채우는 경우의 수는 바로 앞 두 자리의 값에 따라 달라집니다. arr[i-1]이 1이 아닌 경우 i번째 자리에는 (max_val - 2)가지 선택지가 남고, arr[i-2]가 1이 아닌 경우에는 (max_val - 1)가지 선택지가 남습니다.
이를 정리하면 다음과 같은 점화식을 얻습니다.
arr[i] = (max_val - 2) × arr[i-1] + (max_val - 1) × arr[i-2]
last_element가 1이라면 마지막 바로 앞 요소는 1이 될 수 없으므로 count = (max_val - 1) × arr[size - 2]로 계산하고, 그렇지 않다면 arr[size - 1]을 그대로 결과로 사용합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
#define Max_N 109

int diff_val(int size, int max_val, int last_element) {
    int count = 0;
    int arr[Max_N] = {
        0
    };
    arr[0] = 0;
    arr[1] = 1;
    for (int i = 2; i < size; i++) {
        int temp_1 = (max_val - 2) * arr[i - 1];
        int temp_2 = (max_val - 1) * arr[i - 2];
        arr[i] = temp_1 + temp_2;
    }
    if (last_element == 1) {
        count = (max_val - 1) * arr[size - 2];
    } else {
        return arr[size - 1];
    }
    return count;
}
int main() {
    int size = 5;
    int max_val = 3;
    int last_element = 3;
    cout << "Count of arrays having consecutive element with different values are: " << diff_val(size, max_val, last_element);
    return 0;
}

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

실행 결과

Count of arrays having consecutive element with different values are: 5

정리

첫 번째와 마지막 요소가 고정되어 있고 인접한 요소들은 서로 달라야 한다는 제약 조건 때문에, 모든 경우를 일일이 확인하는 완전 탐색은 배열 크기가 커지면 비효율적입니다. 반면 동적 계획법을 적용하면 이전 상태의 값을 재활용해 선형 시간 O(size) 안에 답을 구할 수 있으며, 위와 같이 점화식만 명확히 세우면 구현 자체도 매우 간단합니다.