[BOJ 28426] 더하기와 나누기

문제 링크 : https://www.acmicpc.net/problem/28426

문제

다음 두 조건을 만족하는 길이 $N$의 수열 $A_1,A_2,\cdots,A_N$을 아무거나 하나 구해서 출력해 보자.

• 수열의 원소는 모두 다르고 $2$ 이상 $10^6$ 이하의 정수이다.
• $1$ 이상 $N$ 이하의 모든 정수 $i$에 대해서, $A_i$가 $A_1+A_2+\cdots + A_N$의 약수가 되는 정수 $i$는 정확히 $1$개이다.

입력

첫째 줄에 정수 $N$이 주어진다. $(1 \leq N \leq 10^5)$

출력

첫째 줄에 조건을 만족하는 수열 $A_1,A_2,\cdots,A_N$을 공백으로 구분하여 출력한다.

조건을 만족하는 수열은 항상 존재한다.

제한

시간 제한	메모리 제한
1sec	1024MB

---

풀이

길이 $N$의 수열에서 모든 원소가 다르고, 그중 단 하나의 원소만이 전체 합의 약수가 되도록 만드는 수열을 구성하는 문제다. 수열의 원소 범위가 $2$ 이상 $1\,000\,000$ 이하로 넉넉하므로, 특정 성질을 만족하는 수들을 규칙적으로 선택하는 구성적(Constructive) 방법으로 해결할 수 있다.

가장 효율적인 전략은 전체 합 $S$를 홀수로 만들고, 수열에 포함된 짝수들이 홀수인 $S$를 나누지 못하게 설계하는 것이다. 구체적인 방법은 다음과 같다:

1. 합의 성질 조절: 수열에 포함될 숫자들의 합이 $6$으로 나눈 나머지가 $3$이 되도록 고정한다. 이렇게 하면 $S$는 홀수이므로 모든 짝수 원소는 약수가 될 수 없으며, $S$는 $3$의 배수이지만 $6$의 배수는 아니게 된다.
2. 짝수 쌍 생성: $6k-4$와 $6k-2$ 형태의 짝수 쌍을 필요한 만큼 생성한다. 이 두 수의 합은 $12k-6$으로, 항상 $6$의 배수다. 따라서 짝수 쌍들을 아무리 많이 더해도 전체 합의 $6$에 대한 나머지는 변하지 않는다.
3. 홀수 추가: $N$이 홀수라면 짝수 쌍들을 생성한 뒤 마지막에 $3$을 추가한다. $N$이 이라면 짝수 쌍 생성 후 $3$과 $6$을 추가한다.

이 구성을 통해 만들어진 전체 합 $S$의 성질은 아래와 같다:

\[S = \sum A_i \equiv 3 \pmod 6\]

결과적으로 $3$은 항상 $S$의 약수가 되지만, 함께 포함된 $6$이나 다른 모든 짝수들은 홀수인 $S$의 약수가 될 수 없다. 또한 원소들이 $6k$ 부근에서 생성되므로 $N = 100\,000$일 때도 최대 원소 값이 약 $600\,000$ 수준에 머물러 문제의 범위를 충족한다.

소스코드

Github Link : Source Code

참고 알고리즘 :