시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 35 | 9 | 8 | 33.333% |
한 수열의 부분수열은 주어진 수열에서 몇 개의(1개 이상) 숫자를 제거하여 얻어진 수열을 말한다. 이때 제거하는 수들이 꼭 연속적일 필요는 없다. 예를 들어 1234의 부분수열로는 1, 2, 12, 13, 24 등이 있지만, 1234는 제거한 숫자가 없으므로 부분수열이 아니다.
약수부분수열이란, 부분수열이 나타내는 수가 동시에 약수인 것을 의미한다. 예를 들어 8013824의 약수부분수열로는 8, 13, 14 등이 있다.
입력으로 한 자연수 N이 주어졌을 때, N에서 약수부분수열을 하나 제거해 다음 수 N[2]를 만든다. 이 N[2]에서 약수부분수열을 또 하나 제거하면 N[3]를 만들 수 있고, N[3]에서 약수부분수열을 또 하나 제거하면 N[4]를 만들 수 있다. 이와 같은 과정을 더 이상 다음 수를 만들 수 없을 때까지 반복하면 N, N[2], …, N[k]와 같은 수열을 얻을 수 있다. 이때 k를 최대로 하려고 한다.
8013824와 같은 경우에는 약수부분수열 80을 제거하여 N[2]=13824을 얻고, N[3]=1324, N[4]=132, N[5]=12, N[6]=1을 얻는다. 이때 k=6이 되고, 이 경우가 k가 제일 커지는 경우이다.
첫째 줄에는 자연수 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.
첫째 줄에 차례로 N, N[1], N[2], …, N[k]를 출력한다.
8013824
8013824 13824 1324 132 12 1
7457762
7457762 5772 77 7