DP
-
[백준/JAVA] 1463번 1로 만들기 - Dynamic ProgrammingETC/Algorithm 2023. 5. 27. 23:48
문제 3가지 방법 3으로 나눠지면 3으로 나누고 2로 나눠지면 2로 나누고 위의 2 방법이 안되면 1빼기 풀이 주의점 최소 연산 횟수를 구하기 위해 큰 수를 먼저 나누면 안된다. ex) 10 (2나누기) -> 5 (1빼기) -> 4 (2나누기) -> 2 (1빼기) -> 1 원하는 계산이 안된다. 예시 점화식의 시작은 2부터이다. 배열 arr[0] = arr[1] = 0으로 초기화 후 시작한다. arr[2]의 경우 2로도 나눠지지만 문제에서 1보다 큰 값이 N으로 주어지므로, 1을 뺀 값에 1을 더하여 값을 저장한다. arr[3]의 경우 3으로도 나눠진다. 여기서 Math.min(arr[i], arr[i / 3] + 1)이 사용된다. 둘 중 최솟값을 1을 더하여 저장한다. arr[6]의 경우 2와 3 둘 ..