프로그램 명: ccc_solitaire(open)
제한시간: 5 초
소수 솔리테르는 1에서 시작해 특정 연산을 통해 n에 도달하는 게임입니다. 이 연산은 지금 숫자가 c라고 했을 때 c= a*b를 만족하는 두 숫자로 나눠 비용 b를 들여 c에 a를 더해 다음 숫자로 넘어갈 수 있습니다. n에 도달할 때 까지 이 연산을 반복하는데 가장 적은 비용을 들여 n에 도달하려 합니다.
예를들어 15에 도달하기 위해선
-
1에서 시작
-
1에서 2로 (1+1 = 2, 여기까지 총 비용 1)
-
2에서 3으로 (2+1 = 3, 여기까지 총 비용 1+2)
-
3에서 6으로 (3+3 = 6, 여기까지 총 비용 1+2+1)
-
6에서 12로 (6+6 = 12, 여기까지 총 비용 1+2+1+1)
-
12에서 15로 (12+3 = 15, 여기까지 총 비용 1+2+1+1+4)
따라서 총 비용은 1+2+1+1+4 = 9가 됩니다. 그리고 이 방법이 15에 최소비용으로 도달하는 방법이기도 합니다.
입력
첫 번째 줄에 N이 입력됩니다. (1 ≤ N ≤ 5000000)
출력
첫 번째 줄에 N에 도달하는 최소 비용을 출력하세요.
입출력 예
입력
15
출력
9
입력
2013
출력
91
입출력 설명
2013에 최소 비용으로 도달하는 방법은 2->4->5->10->15->30->60->61->122->244->305->610->671->1342->2013
출처:CEMC (CCC 2013 Stage 1)
번역:ladown21
[질/답]
[제출 현황]
[푼 후(2)]