[백준BOJ] 12852번 1로 만들기2.java

 

백준 저지에서 1로 만들기2를 자바를 통해 풀어 보았다. 

 

https://www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

 

12852번 1로 만들기2.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

12852번  1로 만들기2

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

설명

함수를 bfs라고 쓰긴 했지만 백트래킹에 더 가까운 것 같다. 전체적으로 백트래킹+dp 문제이다.

 

dp를 통해 N부터 1에 다다르는 경우를 구한다. 그 과정을 리스트에 저장하며 백트래킹을 진행한다.

 

1에 도달했을 때의 모든 경우를 비교한다. 그 중 최솟값을 출력한다.

코드

//12852번 1로 만들기2.java
package boj20211213;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class 일로_만들기2_12852 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int answerMin;
    static List<Integer> answerList;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
    	int N = Integer.parseInt(br.readLine());
		int[] dp = new int[N+1];
		
		answerMin = 1000000;
		answerList = new ArrayList<>();
		
		dp[N]=1;
		List<Integer> arr = new ArrayList<>();
		
		bfs(N, arr, dp);
		
		sb.append(answerMin+"\n");
		sb.append(N+" ");
		for(int i=0;i<answerList.size();i++)sb.append(answerList.get(i)+" ");
		System.out.println(sb.toString());
		
	}
    
    static void bfs(int N, List<Integer> arr, int[] dp) {
    	if(N==1) {
    		if(answerMin > arr.size()) {
    			answerMin = arr.size();
    			answerList = new ArrayList<>();
    			for(int i=0;i<arr.size();i++)answerList.add(arr.get(i));
    		}
    		return;
    	}
    	if(N%3==0) {
    		if(dp[N/3]==0 || dp[N/3] > dp[N]+1) {
    			dp[N/3] = dp[N]+1;
    			arr.add(N/3);
    			bfs(N/3, arr, dp);
    			arr.remove(arr.size()-1);
    		}
    	}
    	if(N%2==0) {
    		if(dp[N/2]==0 || dp[N/2] > dp[N]+1) {
    			dp[N/2] = dp[N]+1;
    			arr.add(N/2);
    			bfs(N/2, arr, dp);
    			arr.remove(arr.size()-1);
    		}
    	}
    	if(dp[N-1]==0 || dp[N-1] > dp[N]+1) {
    		dp[N-1] = dp[N]+1;
    		arr.add(N-1);
    		bfs(N-1, arr, dp);
    		arr.remove(arr.size()-1);
    	}
    }
}