[백준] 12852 1로 만들기 2#JAVA

[백준] 12852 1로 만들기 2#JAVA

---

코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		
		int[] d = new int[n+1];	// 최소 횟수 저장
		int[] path = new int[n+1];	//경로 저장
		Arrays.fill(d, Integer.MAX_VALUE);//초기화
		
		d[1] = 0;
		for (int i = 2; i <= n; i++) {

			if(i%3 == 0) {
				if(d[i/3] +1 < d[i]) {
					d[i] = d[i/3] +1;
					path[i] = i/3;
				}
			}
			if(i%2 == 0) {
				if(d[i/2] +1 < d[i]) {
					d[i] = d[i/2] +1;
					path[i] = i/2;
				}
			}
			
			if(d[i-1] +1 < d[i]) {
				d[i] = d[i-1] +1;
				path[i] = i-1;
			}
			
		}
		
		sb.append(d[n]+"\n");
		
		while (n > 0) {
			sb.append(n+" ");
			n =path[n];
			
		}
		
		System.out.println(sb.toString());
		
	}

}

 

 

풀이

---

• DP
• 최단 경로를 저장하는 배열을 생성하여 경로 저장

 

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)