[백준/JAVA] 16953번: A → B
🔺 문제
16953번: A → B
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
www.acmicpc.net
🔺 코드
|
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
|
import java.util.*;
import java.io.*;
public class Main {
static long A, B;
static int cnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
A = Long.parseLong(st.nextToken());
B = Long.parseLong(st.nextToken());
System.out.println(BFS(A));
}
static long BFS(long n) {
Queue<Long> queue = new LinkedList<>();
queue.add(n);
while(!queue.isEmpty()) {
int size = queue.size(); // 현재 큐 크기 미리 저장해둬야 함!!!
for(int i = 0 ; i < size ; i++) {
long now = queue.poll();
if(now == B) {
return cnt + 1;
}
if(now * 2 <= B) queue.add(now * 2);
if(now * 10 + 1 <= B) queue.add(now * 10 + 1);
}
cnt++;
}
return -1;
}
}
|
cs |
✅ 해결 아이디어
✔ DFS / BFS
💥 유의사항
• 23번째 줄 ⇨ 현재 큐 크기 변수 미리 저장해두고 사용해야 함!!! 이래야 해당 크기만큼 반복해 한 단계씩 진행하면서 같은 단계의 노드들 올바르게 처리 가능.
(안 그러면 한 단계 노드들을 모두 처리하기 전에 큐의 크기가 계속 변해, 예상치 못한 동작이 발생한다 함)
🔺 다른 풀이들
- [그리디] B에서부터 줄여가는 접근 방법으로 거꾸로 푸셨다.
[백준 16953] A → B with JAVA
www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장
waristo.tistory.com
[BOJ] 백준 16953번 : A -> B (JAVA)
문제의 링크 : https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를
steady-coding.tistory.com
- [DFS]
[백준] 16953번 A->B (자바 풀이)
문제 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 풀이 이 문제는 재귀 함수를 이용해 간단하게 해결 할 수 있다. 1. 2를 곱한다 -> A*2 2. 1을 수의 가장 오른쪽에 추가한다
code-lab1.tistory.com
💬 느낀 점
인접 행렬 / 리스트도, 방문 배열도 필요 없고
생각보다 정답 코드가 간단해서 조금 놀랐다
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V |
(참고)
백준 16953번( 자바 )
백준 16953번을 자바로 풀어보자 ( 자바 )
velog.io