문제 개요
숫자 n이 주어졌을 때, 크기가 n인 배열 A를 찾아야 합니다. 총 n개의 테이블이 있으며, 각 테이블에는 의자가 4개씩 배치되어 있고, 의자에는 1부터 4n까지 번호가 매겨져 있습니다.
번호가 a와 b(a ≠ b)인 의자에 앉은 두 아이는 다음 조건 중 하나라도 만족하면 서로 장난을 치게 됩니다.
- gcd(a, b) = 1 인 경우 (두 수가 서로소)
- a가 b를 나누거나, b가 a를 나누는 경우
따라서 우리는 어떤 두 아이도 장난을 칠 수 없도록 아이들의 자리를 배정해야 합니다. 다시 말해, 위 조건을 만족하지 않는 의자 번호들의 조합을 찾는 것이 목표입니다.
예를 들어 입력이 n = 4라면, 출력은 [14, 10, 12, 8]이 됩니다. 물론 정답은 여러 가지가 가능합니다.
해결 접근 방식
이 문제의 핵심은 2n부터 4n 미만 사이의 짝수들만 선택하는 것입니다. 그 이유는 다음과 같습니다.
- 이 범위의 모든 짝수는 최소 공약수가 2 이상이므로, 임의의 두 수의 gcd가 절대 1이 될 수 없습니다.
- 범위가 [2n, 4n)으로 제한되기 때문에, 가장 작은 수의 2배조차 4n 이상이 됩니다. 따라서 어떤 수도 다른 수의 배수가 될 수 없습니다.
즉, 단순히 2n부터 시작하여 2씩 증가시키며 4n 미만까지 출력하기만 하면 조건을 만족하는 답을 얻을 수 있습니다.
알고리즘 의사 코드
i := 2 * n 으로 초기화
i < 4 * n 인 동안 반복:
i 출력
i := i + 2
C++ 구현 예제
아래는 실제 동작하는 C++ 코드입니다.
#include <bits/stdc++.h>
using namespace std;
void solve(int n){
for (int i = (2 * n); i < 4 * n; i = i + 2){
cout << i << ", ";
}
}
int main(){
int n = 4;
solve(n);
}
입력
4
출력
8, 10, 12, 14,
마무리
이 문제는 복잡한 탐색 없이도 수학적 성질을 활용하면 O(n) 시간 안에 간단히 해결할 수 있는 좋은 예시입니다. 짝수만 선택한다는 직관적인 아이디어가 gcd와 배수 조건을 동시에 만족시킨다는 점이 핵심 포인트입니다.