[알고리즘/자바] 백준 1463번 - 1로 만들기
1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net Dynamic Programming을 통해 풀어야하는 문제. 재귀를 통해 정답은 맞출수 있으나, 메모이제이션을 하지 않으면 시간초과가 발생한다. ( 중복된 연산을 제거해야한다 ) 입력으로 10이 주어졌을때 수행방식을 작성해보면 다음과 같다. 여기서 f(n)은 n을 1로만드는 최소 연산횟수. 10이 들어왔을떄 3으로 나눌수 있는지 확인했는데 불가능하다. 그렇기 때문에 나누기2와 빼기1 연산만 수행했다. f(10) = f(5)와 f(9)의 결과중 작은값 + 1 f(10) = min( f(5) , f(1) ) + 1 이므로 f(5) 와 f(1)을 구해야한다. 위의 개념을 코드화 하..
2021.01.07