(22.03.27) (Baekjoon) 12852. 1로 만들기 2

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

12852번: 1로 만들기 2

3가지 연산을 이용하여 n을 1로 만드는 문제다.

 

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

이 3가지 연산을 통해 입력받은 숫자를 1로 만들어야 한다.

그 과정 중 가장 빠르게 갈 수 있는 과정을 구해야 한다.(ex. 10의 경우, 10-9-3-1의 과정으로 1로 갈 수 있다.)

 

이걸 풀 수 있는 방법은 DP와 BFS가 있으며, 이 두가지를 모두 알아본다.

 

 

- 0. 공통

해당 문제에서는 가장 빠른 경로의 숫자 개수와 숫자 구성을 모두 가져와야 하기에,

두 값을 모두 저장하기 위해 static class Node를 사용한다.

static class Node {
		int n; // 경로 길이
		String str; // 경로 구성
		public Node(int n, String str) {
			super();
			this.n = n;
			this.str = str;
		}
	}

 

 

- 1. DP

우선 위에서 선언한 클래스를 자료형으로 가지는 1차원 배열을 만든다.

ar = new Node[n+1];
		for (int i = 0; i <= n; i++) {
			ar[i] = new Node(0,""); // 클래스 배열을 선언하면, 처음의 값은 null임을 알아두자.
		}

구하고자 하는 값은 ar[n].n과 ar[n].str임을 기억하고,

ar[1]의 경우는 반드시 포함되므로 기본 값으로써 각각 1과 "1"을 넣어준다.

ar[1].n = 1; // 1이라는 경로는 반드시 포함되어야 한다.
ar[1].str = Integer.toString(ar[1].n); // Integer값을 문자열로 변환한다. "1"로 넣어도 상관 X

이제 2부터 n까지 for문을 돌려서 각 숫자로 갈 수 있는 경로가 있는지 찾는 과정을 진행한다.

 

1- 1을 빼는 경우는 현재 수가 1보다 큰 한 반드시 추가될 수 있으므로 경로에 추가한다.

ar[i].n = ar[i-1].n+1;
ar[i].str = Integer.toString(i) + " " + ar[i-1].str; //경로를 기록할 때, 현재 만난 값이 앞에 오게 경로를 기록한다.

2- 2를 나누는 경우

n이 2로 나누어떨어질 때 시행하면 된다.

if(i % 2 == 0)
    if(ar[i].n > ar[i/2].n) {
        ar[i].n = ar[i/2].n+1;
        ar[i].str = Integer.toString(i) + " " + ar[i/2].str;
    }

 

3- 3을 나누는 경우

n이 3으로 나누어떨어질 때 시행하면 된다.

if(i % 3 == 0) {
    if(ar[i].n > ar[i/3].n) {
        ar[i].n = ar[i/3].n+1;
        ar[i].str = Integer.toString(i) + " " + ar[i/3].str;
    }
}

 

위 세가지 연산을 2~n 반복문 안에서 시행한다.

for (int i = 2; i <= n; i++) {
			ar[i].n = ar[i-1].n+1;
			ar[i].str = Integer.toString(i) + " " + ar[i-1].str;
			if(i % 2 == 0)
				if(ar[i].n > ar[i/2].n) {
					ar[i].n = ar[i/2].n+1;
					ar[i].str = Integer.toString(i) + " " + ar[i/2].str;
				}
			if(i % 3 == 0) {
				if(ar[i].n > ar[i/3].n) {
					ar[i].n = ar[i/3].n+1;
					ar[i].str = Integer.toString(i) + " " + ar[i/3].str;
				}
			}
		}

이때 의문점이라 하면,

위 방법으로 할 경우 결국 목표 숫자로 도착하는 경우가 여러가지인데 어떻게 최소인 경우를 고르느냐?

라는 게 생각되는데, 답은 계산의 순서에 있다.

+1만 해서 목표 숫자로 오게 되면 나머지 두 경우보다 많은 경로가 될 것이고, 

나머지 두 경로 중에서도 /3은 /2보다 짧은 경로로 목적지에 도착하게 된다.

 

따라서 위의 3가지 경로를 이동할 때 가장 짧은 경로로써 목표 값에 도달하게 되는 것이다.

 

전체 소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int n;
	static long ans;
	static Node[] ar;
	static Queue<Node> q = new LinkedList<Node>();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		ar = new Node[n+1];
		for (int i = 0; i <= n; i++) {
			ar[i] = new Node(0,"");
		}
		
		ar[1].n = 1;
		ar[1].str = Integer.toString(ar[1].n);
		for (int i = 2; i <= n; i++) {
			ar[i].n = ar[i-1].n+1;
			ar[i].str = Integer.toString(i) + " " + ar[i-1].str;
			if(i % 2 == 0)
				if(ar[i].n > ar[i/2].n) {
					ar[i].n = ar[i/2].n+1;
					ar[i].str = Integer.toString(i) + " " + ar[i/2].str;
				}
			if(i % 3 == 0) {
				if(ar[i].n > ar[i/3].n) {
					ar[i].n = ar[i/3].n+1;
					ar[i].str = Integer.toString(i) + " " + ar[i/3].str;
				}
			}
		}
		System.out.println(ar[n].n-1);
		System.out.println(ar[n].str);
	}

	static class Node {
		int n;
		String str;
		public Node(int n, String str) {
			super();
			this.n = n;
			this.str = str;
		}
		
	}
}