문제
https://www.acmicpc.net/problem/25418
풀이
문제를 간단히 요약하면 입력받은 정수 값 A에 두 가지 연산을 적용해 정수 K로 만드는 것이다. 연산 1은 정수 A에 1을 더하기, 연산 2는 정수 A를 2로 곱하기이다. 처음에는 문제 해결을 위한 아이디어를 다음과 같이 잡았다. 먼저 방문 여부를 체크할 visit 배열과 해당 인덱스까지 몇 번만에 도달할 수 있는지를 저장할 arr를 선언한다. 이후 bfs 메소드를 만들어 인자로 정수 n을 받아, arr[n * 2]가 방문하지 않은 상태라면 arr[n] + 1의 값을 저장한다. 그리고 n * 2에 bfs를 다시 걸어 n * 2를 기준으로 bfs를 또 실행한다. 마찬가지로 arr[n+1]이 방문하지 않은 상태라면 arr[n] + 1의 값을 저장하고 방문 처리를 하고, n + 1에도 bfs를 또 실행한다. 그런데 너무 오랜만에 PS를 하니 이게 DFS인지도 모르고 무작정 예제 입력을 넣으니 스택 오버플로우가 터졌다. 그래서 BFS를 구현한 방식을 최대한 떠올려 간신히 큐를 이용해 BFS를 구현한걸 기억해내서 아래와 같이 큐를 이용해 구현하였다.
따라서 다음과 같이 구현을 하였다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static Queue<Temp> q;
public static boolean[] visit;
public static int k;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
q = new LinkedList<>();
int n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
visit = new boolean[k+1];
q.add(new Temp(n, 0));
visit[n] = true;
while (! q.isEmpty()) {
Temp t = q.poll();
int idx = t.n;
int cnt = t.count;
if (idx == k) { System.out.println(cnt); break; }
if (idx * 2 <= k && !visit[idx * 2]) {
q.add(new Temp(idx * 2, cnt + 1));
visit[idx * 2] = true;
}
if (idx + 1 <= k && !visit[idx + 1]) {
q.add(new Temp(idx + 1, cnt + 1));
visit[idx + 1] = true;
}
}
}
public static class Temp {
int n;
int count;
public Temp(int n, int count) {
this.n = n;
this.count = count;
}
}
}
|
cs |
코드를 살짝 뜯어보자. 문제에서 제공되는 A는 그냥 n으로 사용하였다. Temp 클래스는 인덱스로 사용할 n과 n까지 도달 가능한 횟수를 저장하는 count 필드를 가진다. 입력 값 n까지는 바로 도달할 수 있으니 count를 0으로 하여 큐에 넣어준다. 이제 while 반복문을 통해 bfs를 구현했는데 큐에서 하나 뺀 뒤에 n의 값을 먼저 확인한다. 뺐는데 인덱스가 k라면 이미 도착한거니 도달하는 횟수인 cnt를 출력하고 break를 걸어주면 된다. 만약 아니라면, 위의 두 연산을 차례로 진행해서 큐에 넣어주면 된다. 큐에 넣어줄 때에도 n에 2를 곱한 값 / n + 1에 이미 도착하였는지 체크를 하고 넣어준다. 이제 이 탐색을 큐가 빈 상태까지 반복해주면 된다. 큐가 빌 때까지 반복을 하여도 어차피 n이 k 값이 되면 중간의 if 구문을 통해 종료되므로 상관이 없다.
'PS > Solve' 카테고리의 다른 글
[Java] Boj 14496: 그대, 그머가 되어 (2) | 2025.07.11 |
---|---|
[Java] Boj 6528: 106 miles to Chicago (0) | 2025.03.13 |
[Java] Boj 24052: 알고리즘 수업 - 삽입 정렬 2 (0) | 2025.03.11 |
[Java] Boj 24051: 알고리즘 수업 - 삽입 정렬 1 (0) | 2025.03.11 |
[Java] Boj 23882: 알고리즘 수업 - 선택 정렬 2 (0) | 2025.03.11 |