문제
https://www.acmicpc.net/problem/12852
풀이
1로 만들기 풀이와 유사하지만, x에서 1까지 어떤 숫자를 선택했는지를 저장해야 한다.
next[x]는 x 다음 ( /3, /2, -1) 연산을 통해 어떤 숫자가 되어야 최소 작업으로 1이 될 수 있는 지를 저장한다.
package boj.dp; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Boj_12852_1로만들기2 { static int[] d; static int[] next; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int x = Integer.parseInt(br.readLine()); d = new int[x+1]; d[1] = 0; next = new int[x+1]; int min = dp(x); // 답 도출 StringBuilder sb = new StringBuilder(); sb.append(min).append("\n"); int nextNum = x; while(nextNum >= 1) { sb.append(nextNum).append(' '); nextNum = next[nextNum]; } System.out.println(sb); br.close(); } public static int dp(int x) { if(d[x] > 0 || x<=1) { return d[x]; } int min = Integer.MAX_VALUE; if(x%3 == 0) { if(min > dp(x/3)+1) { min = d[x/3]+1; next[x] = x/3; } } if(x%2 == 0) { if(min > dp(x/2)+1) { min = d[x/2]+1; next[x] = x/2; } } if(min > dp(x-1)+1) { min = d[x-1]+1; next[x] = x-1; } return d[x] = min; } }
'알고리즘 > 문제 풀이' 카테고리의 다른 글
[프로그래머스] Lv.2 시소 짝꿍 (Java) (0) | 2025.01.08 |
---|---|
[백준] BOJ 2579번 계단 오르기 (Java) (1) | 2024.11.15 |
[프로그래머스] Lv.2 두 큐 합 같게 만들기 (Java) (1) | 2024.11.12 |
[프로그래머스] Lv.3 길 찾기 게임 (Java) (1) | 2024.11.08 |