Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- BinarySearch
- 백트래킹
- 스프링
- Java
- 항해99
- 코딩테스트준비
- 데이터베이스
- 완전탐색
- 백준
- BFS
- 브루트포스
- 트리
- 네트워크 계층
- DFS
- 정렬
- Spring
- 그래프 이론
- 우선순위큐
- DP
- 그래프
- 스프링 핵심 원리 - 기본편
- lower bound
- 자바
- Til
- 프로그래머스
- 99클럽
- 그리디
- 동적 프로그래밍
- 개발자취업
- 알고리즘
Archives
- Today
- Total
AtraFelis's Develop Diary
[백준] 16953 - A → B (JAVA) 본문
문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B ($1 ≤ A < B ≤ 10^9$)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
풀이
BFS를 이용하여 최소 연산 횟수를 찾는 문제이다. 주의할 것은 B의 최댓값이 $10^9$이므로, 오버플로우가 일어날 수 있다는 것이다.
첫 번째 연산인 $num \times 2$일 때는 int의 최댓값인 $2^{31}-1$을 초과하지 않지만, 두 번째 연산에서는 오버플로우가 일어날 수 있으므로 64bit 자료형인 long
을 사용하거나, unsigned int
를 사용해야 한다. 하지만 자바에서는 unsigned int
를 자료형으로 지원하지 않으므로 long
을 사용해야 한다.
자연스럽게 visited를 사용해서 중복체크를 해주었는데, 다른 분들의 코드를 보니 이 문제에서는 visited가 없어도 시간 초과가 일어나지 않는 듯하다. 그래도 일단 설명을 해보자면, visited를 여타 다른 문제처럼 배열을 이용해서 사용한다면 최대 $10^9$의 크기의 배열이 필요하게 된다. 그렇기에 map을 사용하여 visited 체크를 해주면 된다.
전체 코드
import java.io.*;
import java.util.*;
public class Main {
static int
static long mul(long n) {
return n*2L;
}
static long add_right(long n) {
return n * 10L + 1;
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(bf.readLine());
long A = Integer.parseInt(stk.nextToken());
long B = Integer.parseInt(stk.nextToken());
Deque<Long[]> deque = new ArrayDeque<>();
Long[] value = { A, 1L };
deque.add(value);
Map<Long, Boolean> visited = new HashMap<>();
while(!deque.isEmpty()) {
value = deque.removeFirst();
if(value[0] == B) {
System.out.println(value[1]);
return;
}
Long[] next_value;
long res;
if((res = mul(value[0])) <= B && !visited.getOrDefault(res, false)) {
next_value = new Long[]{res, value[1] + 1};
deque.add(next_value);
visited.put(res, true);
}
if((res = add_right(value[0])) <= B && !visited.getOrDefault(res, false)) {
next_value = new Long[]{res, value[1] + 1};
deque.add(next_value);
visited.put(res, true);
}
}
System.out.println(-1);
}
}
'Algorithm > 백준' 카테고리의 다른 글
[백준] 1005 - ACM Craft (JAVA) (0) | 2024.06.24 |
---|---|
[백준] 12865 - 평범한 배낭 (JAVA) (0) | 2024.05.21 |
[백준] 11725 - 트리의 부모 찾기 (JAVA) (0) | 2024.05.05 |
[백준] 20529 - 가장 가까운 세 사람의 심리적 거리 (C언어) (0) | 2024.04.16 |
[백준] 5525 - IOIOI (C언어) (0) | 2024.04.14 |