[백준] 28426 더하기와 나누기

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

풀이 및 구현

수열의 원소 중에서 1개만 수열의 합의 약수가 되어야 한다. 그래서 처음 원소를 약수로 고정하고 원소들을 추가할 때 추가한 원소가 약수가 되지 않으면서 첫 원소가 약수가 되도록 추가하면 될 것이라 생각했다.

홀수와 짝수의 개념을 떠올리면 이를 쉽게 구현할 수 있다.

시작 수를 홀수로 놓고 계속해서 짝수를 더한다면 합은 항상 홀수이므로 시작 원소를 제외한 나머지 원소들은 약수가 되지 않는다. 이때 합이 계속해서 시작 수의 약수가 되어야 하는데 이를 만족하는 숫자를 찾아보면 3과 6의 배수가 있다.

시작 수를 3으로 놓고 6의 배수들을 더하면 합이 항상 홀수이면서 3의 배수이기 때문에 6의 배수들이 약수가 될 수 없어 문제의 조건을 만족한다.

$N \geq 1$ 이므로 처음 3을 출력하고 남은 횟수만큼 6의 배수를 출력해주면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int N; cin >> N;
    cout << 3 << ' ';
    for (int i = 1; i < N; i++) cout << i * 6 << ' ';

}

후기

다양한 풀이가 존재하는 문제다.

2와 4의 배수를 활용하면 짝수만 사용해서도 문제를 해결할 수 있다!