1차 풀이 (2018-08-05, 5892 KB, 4 MS) |
무식하게 위에서부터 전부 계산하자.
int *S 이라는 배열을 하나 선언하고,
S[x]는 x을 만들기 위한 최소횟수라고 정의하자.
입력받은 N에서부터 1까지 내려오면서,
모든 S[x]를 항상 최소로 갱신시키면,
S[1]은 해당 케이스의 결과를 가르킨다.
큰 배열은 동적할당을 사용하자.
크기가 100001인 배열을 생성했을 때,
정적배열은 런타임 오류가 발생했지만,
동적배열은 정상적으로 실행되었다.
2차 풀이 (2018-08-05, 1984 KB, 0 MS) |
최적 부분 구조에 눈치채자.
정답인 최소 연산횟수를 반환하는 함수를 count(n) 이라고 하자.
count(n)을 풀기 위해서 우리는 3가지 연산을 사용할 수 있는데,
각각의 연산을 사용할 때 마다, 작은 부분문제가 생긴다.
1번 연산 → count(n/3)
2번 연산 → count(n/2)
3번 연산 → count(n-1)
위의 부분문제는 count(n)와는 전혀다른 독립적인 문제이며,
부분문제가 항상 최적인 결과를 반환한다고 가정했을 때,
자연스럽게 전체문제도 최적으로 이어지기 때문에,
이 문제는 최적부분 구조를 가졌다는 것을 알 수 있다.
최적 부분구조를 가진 문제는
동적 계획법을 사용하여 해결할 수 있다.
1을 연속으로 빼는것은 아웃.
1을 빼는 연산만을 사용하는 방법은
최적해가 될 수 없음을 직관적으로 알 수 있다.
1을 빼는 연산은 제한적으로 사용되어야 하며,
나누기 연산을 사용하기 위해 활용되어야 함을 깨달아야 한다.
ex)
10 5 4 2 1 // 나누기 연산을 우선적으로 처리.
10 9 3 1 // 1을 빼어 3의 배수로 만듦.
배수로 만들어 나누자.
결과적으로 정수 n에 대하여 가능한 방법은 다음과 같다.
- 3의 배수로 만들고, 재귀에 넘긴다.
- 2의 배수로 만들고, 재귀에 넘긴다.
배수를 만드는 과정에 1을 빼는 연산이 포함되어 있으므로,
추가적인 카운트를 가산하고 난 뒤에, 두개 중 최소값을 선택하여 반환한다.
