C++로 모든 부분 배열이 '좋은 배열'인 크기 n의 완벽한 배열 찾기

문제 설명

숫자 n이 하나 주어진다고 가정해 봅시다. 어떤 배열 B의 원소들의 합이 그 배열의 길이로 나누어 떨어질 때, 배열 B를 좋은 배열(good array)이라고 부릅니다. 또한, 크기가 n인 배열 A의 모든 비어 있지 않은 부분 배열(subarray)이 좋은 배열이고, 배열 A의 각 원소가 1부터 100 사이의 범위에 있을 때, 배열 A를 완벽한 배열(perfect array)이라고 정의합니다. 우리는 숫자 n이 주어졌을 때, 이러한 조건을 만족하는 완벽한 배열 A를 구해야 합니다.

예를 들어 입력이 n = 4라면, 출력으로 [7, 37, 79, 49]와 같은 배열을 만들 수 있습니다. 물론 정답은 여러 개 존재할 수 있습니다.

접근 방법

이 문제를 해결하기 위해 다음 단계를 따릅니다 −

for initialize i := 0, when i < n, update (increase i by 1), do:
    print 1

즉, 숫자 1을 n번 출력하면 됩니다. 그 이유는 다음과 같습니다. 길이가 k인 부분 배열이 모두 1로만 이루어져 있다면, 그 원소들의 합은 정확히 k가 되고, 이는 배열의 길이 k로 나누어 떨어집니다. 따라서 모든 부분 배열이 자동으로 좋은 배열이 되며, 원소 값 1은 문제에서 요구하는 범위(1~100) 안에 있으므로 완벽한 배열의 조건을 모두 충족하게 됩니다.

예제 코드

더 나은 이해를 돕기 위해 다음 구현 예시를 살펴보겠습니다 −

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

void solve(int n){
    for(int i=0;i<n;i++){
        cout<<"1"<<", ";
    }
}
int main(){
    int n = 4;
    solve(n);
}

입력

4

출력

1, 1, 1, 1,

복잡도 분석

시간 복잡도: O(n) — n개의 원소를 한 번씩 출력합니다.
공간 복잡도: O(1) — 추가적인 저장 공간이 필요하지 않습니다.