[JAVA/자바] 백준 1463번: 1로 만들기

<문제> <풀이> dp 문제를 많이 접하지 못해서 어려웠던 문제다.. 다이나믹 프로그래밍에는 Top-Down(재귀 함수) 방식과 Bottom-Up(반복문) 방식이 있는데 Bottom-Up 방식이 일반적인 방법이라고 한다.

문제를 풀기에 앞서 여러 블로그를 참고했지만 내가 가장 이해하기 쉬웠던 알고리즘으로 풀이했다. 1~1000000사이의 수가 주어지므로 1000001크기의 배열을 선언한다. 세 가지 경우의 수가 주어지는데 1. 1을 빼라 (arr[i-1] + 1) 2. 2로 나누어떨어지면 2로 나눠라 (arr[i/2] + 1) 3. 3으로 나누어떨어지면 3으로 나눠라 (arr[i/3] + 1) 이때 1을 뺀 값, 2로 나눈 값, 3으로 나눈 값 중 최솟값이 arr[i]의 값이 된다. if(i % 2 &#x..........