"Factor Salitaire" 게임은 숫자 1에서 시작해 목표 숫자(n) 까지 반복적으로 숫자를 바꿔가는 게임이다.
...
현재 숫자가 c일때, c = a * b의 관계를 가지는 양의 정수 a, b 수 중에 하나를 고를 수 있는데,
a를 골랐을 때에는 현재 숫자 c에 a를 더해 새로운 숫자가 만들어진다.
그리고, 이렇게 했을 경우 b 만큼의 비용(points)이 필요하다.
...
이런 작업을 계속해가며 주어진 목표 숫자까지 진행해가면 되는데,
이때, 필요한 최소 비용(points)을 계산해보자.
...
예를 들어 목표 숫자 15을 얻기 위한 방법은 아래와 같다.
- 1로 시작한다.
- 1 을 ... 1+1=2 로 바꾸면 : 1점이 필요하다.
- 2 를 ... 2+1=3 로 바꾸면 : 여기까지 1+2 점이 필요하다.
- 3 을 ... 3+3=6 으로 바꾸면 : 여기까지 1+2+1 점이 필요하다.
- 6 을 ... 6+6=12 로 바꾸면 : 여기까지 1+2+1+1 점이 필요하다.
- 12를 ... 12+3=15 로 바꾸면 : 목표 숫자 15가 완성되고, 여기까지 1+2+1+1+4 = 9 점이 필요하다.
...
그리고 사실은.. 이 방법이 숫자 15를 얻기 위한 최소 비용 방법이다.