백준 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$개이다.

풀이

고민을 많이해서 푼 문제이다.
처음에는 수열의 합과 나머지 연산을 이용해서 하나의 수식으로 정리하려고 했지만, 아무리 해도 나오지 않았다.

골드5 난이도면 분명 어떤 아이디어가 있을 것이라고 생각을 했고, 정수로 이루어진 수열의 합과 수열의 원소 중 하나가 약수가 된다는 점에 초점을 두었다.
그리고 해 구성하기/구성적 이라는 특성을 통해 이를 이용해서 특정 규칙을 이용한 수열을 만들면 풀 수 있을 것 이라고 생각을 했다.

여러가지 시도 끝에 홀수와 짝수를 이용해야 한다는 것을 알게 되었다.
홀수는 무조건 홀수로만 나눌 수 있다. 그리고 홀수 + 짝수는 홀수가 된다.
그러면 어떤 수열에서 하나의 원소가 홀수이고, 나머지 원소가 짝수면 결국 이 문제의 조건에 들어맞게 된다.

그래서 나는 시작 원소를 3으로 하고, 2부터 시작해서 모든 짝수를 수열에 넣고 체크하는 방식으로 코드를 구현했다. 이떄 고려해야할 점은 N의 최대가 10^6 이라는 점이다. 각각의 원소도 또한 10^6 이하이고, 결국 10^6이하의 숫자들의 나열로 과연 10^6의 N을 만족시킬 수 있는지가 마지막 걸림돌이었다.

완전탐색을 통해 체크해보니 N이 10^6일때 마지막 원소가 10^5*5 + a 가 나오는 것을 알 수 있었다. 그러므로 이 풀이로 이 문제를 풀수 있다는 것이 성립하였다.