백준 28426 - 더하기와 나누기 (C++)

문제

• 문제 링크

  
   BOJ 28426 - 더하기와 나누기 
  

• 문제 요약

수열의 원소는 모두 다르고 $2$ 이상 $10^6$ 이하의 정수이다.

$1$ 이상 $N$ 이하의 모든 정수 $i$에 대해서, $A_i$가 $A_1 + A_2 + ... + A_N$의 약수가 되는 정수 $i$는 정확히 $1$개이다.


$N$이 주어지면, 위 조건을 만족하는 수열을 아무거나 하나 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N ≤ 10^5$

알고리즘 분류

• 해 구성하기 (constructive)

풀이

홀수와 짝수에 집중해보면 된다.
$N-1$개의 짝수와, $1$개의 홀수로 수열을 구성하는 것을 생각하자.

홀수의 기준을 $3$으로 잡으면, 다음과 같이 진행되는 수열을 만들어 볼 수 있다.

$3$ $2$ $4$ $6$ $8$ $10$ $...$

한가지 유의 사항으로, 단순히 위처럼 답을 내면 $N$을 $3$으로 나눈 나머지가 $2$일 때 $A_1 + A_2 + ... + A_N$가 $3$으로 나누어 떨어지지 않는 경우가 발생한다.

이를 테면 $N = 2, 5, 8, ...$과 같은 상황이다.

결과적으로 이 경우에선, $A_N$에 $4$를 더해줌으로써 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
 
int main()
{
    int n, i(2); scanf("%d", &n);
 
    printf("3 ");
    for (int _n(n - 1); --_n > 0; i += 2)
        printf("%d ", i);
    if (n > 1) printf("%d", i + (n % 3 == 2 ? 4 : 0));
}

comment

끝