[Baekjoon] 12852_1로 만들기 2

Silver I

문제(출처: https://www.acmicpc.net/problem/12852)

---

< 1로 만들기 2 >

 

문제 풀이 

 

입력 범위인 1000000만큼의 배열을 만들어 N을 1로 만드는 경로를 저장한다. 

만약 5에서 1을 빼는 연산을 한다면 4이므로 arr [4] = 5와 같이 전에 값을 저장하는 방법으로 문제를 해결했다.

 

 

 my solution (Java)

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

public class _12852_ { // 1로 만들기 2

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(bf.readLine());
		int arr[] = new int[1000001];

		Queue<int[]> queue = new LinkedList<>();

		if (n != 1) {
			queue.add(new int[] { n, 0 });
		}

		while (!queue.isEmpty()) {
			int num[] = queue.poll();

			if (num[0] % 3 == 0 && arr[num[0] / 3] == 0) {
				queue.add(new int[] { num[0] / 3, num[1] + 1 });
				arr[num[0] / 3] = num[0];
				if (num[0] / 3 == 1) {
					bw.write((num[1] + 1) + "\n");
					break;
				}
			}
			if (num[0] % 2 == 0 && arr[num[0] / 2] == 0) {
				queue.add(new int[] { num[0] / 2, num[1] + 1 });
				arr[num[0] / 2] = num[0];
				if (num[0] / 2 == 1) {
					bw.write((num[1] + 1) + "\n");
					break;
				}
			}
			if (arr[num[0] - 1] == 0) {
				queue.add(new int[] { num[0] - 1, num[1] + 1 });
				arr[num[0] - 1] = num[0];
				if (num[0] - 1 == 1) {
					bw.write((num[1] + 1) + "\n");
					break;
				}
			}
		}

		if (n == 1)
			bw.write("0\n");

		ArrayList<Integer> result = new ArrayList<>();
		int idx = 1;
		while (true) {
			result.add(idx);
			if (idx == n) {
				break;
			}
			idx = arr[idx];
		}

		for (int i = result.size() - 1; i >= 0; i--) {
			bw.write(result.get(i) + " ");
		}
		bw.flush();
	}
}

 

Main

변수)
n : 입력 값 정수
arr : 연산 경로 저장
queue : [연산 값, 연산 횟수]
num : queue에서 뽑아낸 값
result : 답 저장하는 리스트

 

- 입력 값 정수(n) 입력

- queue에 시작 값인 n과 연산 횟수 저장

- queue가 빌 때까지 반복 

1) 3으로 나누어 떨어지며 3으로 나눈 값에 아직 방문한 적이 없으면

: queue에 저장

: arr [정수/3] = 정수 

2) 2로 나누어 떨어지며 2로 나눈 값에 아직 방문한 적이 없으면

: queue에 저장

: arr [정수/2] = 정수

3) 1로 뺀 값에 아직 방문한 적이 없으면

: queue에 저장

: arr [정수-1] = 정수

각 연산을 수행한 후 값이 1이면 연산 횟수 출력 후 바로 종료

- 입력 값이 1이라면 위의 과정을 거치지 않고 바로 연산 횟수 0 출력

- n을 1로 만드는 방법에 포함되어 있는 수를 출력하기 위해 먼저 역순으로 ArrayList에 저장

ex) 2 -> 1이라면 ArrayList에는 1 -> 2로 저장됨

- 답을 출력하기 위해 ArrayList를 거꾸로 출력

---

---