
[BOJ] 문제 풀이 모음집 - DP (JAVA)
·
Algorithm/DP
1463: 1로 만들기🔗 문제 링크1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우를 각각 나누어서 점화식을 세워야 함1을 빼는 경우의 값으로 초기화: dp[i] = dp[i - 1]3으로 나누어지는 경우의 점화식: dp[i] = Math.min(dp[i], dp[i / 3] + 1)2로 나누어지는 경우의 점화식: dp[i] = Math.min(dp[i], dp[i / 2] + 1)BFS 탐색도 가능할 것 같아서 시도했는데 BFS 탐색으로도 최소 연산 횟수를 구할 수 있음탐색하고 있는 수가 1이 되면 탐색을 종료해야 함dist[N]이 아니라, dist[1]의 값이 N에서 1까지의 최소 연산 횟수이므로 주의할 것!더보기24.06.24 풀이DP 풀이import java.io.*;public clas..