CEO

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 문제는 특정 수가 1이 되기 위해서 2, 3으로 나누거나 -1을 하였을 때 최소 횟수로 1을 만드는 방법을 찾는 것이다. 효율적으로 문제를 풀기 위해 메모이제이션(memoization)을 통해 문제를 접근하면 시간초과를 발생시키지 않고 문제를 풀 수 있다. 문제를 푸는 방법은 그림 1과 같다. 그림 1은 10인 경우에 메모이제이션을 통해 값을 찾는 과정이다. 다음과 같은 과정을 반복하여 카운트 값을 누적시켜가는 방식을 사용한다. 각 인덱스는 실제 값을 의미한다. (1 ~ N) 입력된 값과 인덱스를 일치시키기 위해 0번 인덱스를 사용하지 않는다. 입력 값이 1인..