연속된 두 원소가 나누어 떨어지지 않는 정렬 배열 만들기 – C++ 구현

숫자 n이 주어졌다고 가정해 봅시다. 우리는 n개의 원소를 가진 배열 A를 만들어야 합니다. 이때 배열 A는 다음 세 가지 조건을 만족해야 합니다.

• 배열은 오름차순으로 정렬되어 있어야 합니다.
• 모든 원소는 서로 중복되지 않아야 합니다.
• 배열 인덱스가 1부터 시작한다고 할 때, i가 2부터 n까지인 모든 i에 대해 A[i]는 A[i-1]로 나누어 떨어지지 않아야 합니다.

예를 들어 입력이 n = 7이라면 출력은 다음과 같습니다.

[2, 3, 4, 5, 6, 7, 8]

접근 방법

이 문제는 생각보다 아주 간단하게 해결할 수 있습니다. 바로 2부터 n+1까지의 연속된 자연수를 그대로 나열하는 것입니다.

그 이유는 다음과 같습니다. 임의의 자연수 k에 대해 k와 k+1은 연속된 수입니다. k+1을 k로 나누면 몫은 1, 나머지는 항상 1이 되므로 두 수는 절대 나누어 떨어질 수 없습니다. 즉, 연속된 자연수들은 자동으로 '나눌 수 없음' 조건을 만족합니다.

따라서 별도의 복잡한 계산 없이 2부터 n+1까지 숫자를 순서대로 출력하기만 하면 됩니다.

알고리즘 단계

1. 반복 변수 i를 2로 초기화합니다.
2. i가 n+1보다 작거나 같은 동안 반복하며 i를 출력하고 1씩 증가시킵니다.

예제 코드

아래는 위 알고리즘을 C++로 구현한 예제입니다.

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

void solve(int n){
    for (int i = 2; i <= n + 1; i++){
        printf("%d, ", i);
    }
}

int main(){
    int n = 7;
    solve(n);
}

입력

7

출력

2, 3, 4, 5, 6, 7, 8

복잡도 분석

• 시간 복잡도: O(n) — 2부터 n+1까지 한 번씩만 순회하면 됩니다.
• 공간 복잡도: O(1) — 추가적인 저장 공간이 필요하지 않습니다.

이처럼 문제의 조건을 잘 분석하면 연속된 자연수 나열이라는 매우 효율적인 해법을 도출할 수 있습니다.