백준 12852 1로 만들기2 [자바]

in Develop / Solving

baekjoon 12852 1로 만들기2

java

문제 분석

  • 1,000,000 이하의 정수 x가 주어짐.
  • x에 대해 아래 세 개의 연산을 할 수 있음.
    • x가 3으로 나누어 떨어지면, 3으로 나눔.
    • x가 2로 나누어 떨어지면, 2로 나눔.
    • x에서 1을 뺌.
  • 세 연산을 적절히 활용하여, 1에 도달할 수 있는 최소 연산 수와, 그 때 거쳐간 수들을 모두 출력할 것.

입력조건

정수 x

풀이과정

  • 1로 만들기 이 문제 1을 언제 풀었는지 기억이 안나서, 찾아보려다가 그냥 영향을 안 받고 새로 코드를 짜기로 했다.
  • 문제의 출력에 이 수가 거쳐 간 수들을 전부 출력해야 한다.

  • ‘최단거리’라는 점에 집중하여, dp와 bfs를 혼합한 식으로 코드를 작성하기로 하였다.

  • data라는 클래스를 새로 만듬.
    • 이 클래스는 현재까지 한 연산의 수와, 여태까지 지나온 숫자들을 기록할 ArrayList를 가지고 있음.
  • 정수 x를 입력받으면 x+1 크기의 배열을 선언.
  • x부터 각 연산을 진행하면서 1까지 내려간다.
  • 클래스로 된 배열을 선언할 때, 각각에 new로 할당해주지 않으면 객체가 null인 것을 이용하여 방문처리를 진행.
    • 배열의 k번째 위치의 data가 null이면, 여기에 아직 안 와본 것.
  • 위 방법으로 bfs를 진행하여, 1에 도착하면 종료.
  • 1씩 빼면 무조건 1에 도착할 수 있으므로, 예외처리는 필요하지 않음.

코드 구성

  • data 객체

    static class data {
    ArrayList<Integer> path;
    int count;
    data(int count) {
        this.count = count;
        this.path = new ArrayList<>();
    }
}

  • null을 이용한 방문처리

    while(arr[1] == null) {
    int now = que.poll();
  
    for(int idf = 2; idf <= 3; idf++) {
        if(now%idf == 0 && arr[now/idf] == null) {
            // 연산 코드
        }
        if(arr[now-1] == null) {
            // 연산 코드
        }
    }
}

전체 코드

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

public class BJ12852_1로만들기2 {
	static class data {
		ArrayList<Integer> path;
		int count;
		data(int count) {
			this.count = count;
			this.path = new ArrayList<>();
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		data[] arr = new data[n+1];
		
		arr[n] = new data(0);
		arr[n].path.add(n);
		Queue<Integer> que = new LinkedList<Integer>();
		que.add(n);
		while(arr[1] == null) {
			int now = que.poll();
			
			for(int idf = 2; idf <= 3; idf++) {
				if(now%idf == 0 && arr[now/idf] == null) {
					arr[now/idf] = new data(arr[now].count+1);
					arr[now/idf].path.addAll(arr[now].path);
					arr[now/idf].path.add(now/idf);
					que.add(now/idf);
				}
				if(arr[now-1] == null) {
					arr[now-1] = new data(arr[now].count+1);
					arr[now-1].path.addAll(arr[now].path);
					arr[now-1].path.add(now-1);
					que.add(now-1);
				}
			}
		}
		System.out.println(arr[1].count);
		for(int num : arr[1].path)
			System.out.print(num + " ");		
	}
}

추가

  • 생각해보니까, data에 들가있는 배열의 크기가 진행한 연산 수를 알려주니까, 굳이 클래스 안만들고도 풀 수 있었다.