A → B
2 초 | 512 MB | 55712 | 22919 | 18174 | 39.686% |
---|
문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
예제 입력 1 복사
2 162
예제 출력 1 복사
5
2 → 4 → 8 → 81 → 162
예제 입력 2 복사
4 42
예제 출력 2 복사
-1
예제 입력 3 복사
100 40021
예제 출력 3 복사
5
100 → 200 → 2001 → 4002 → 40021
접근법
이 문제는 정수 A를 B로 바꾸기 위해 가능한 두 가지 연산을 이용하여 최단 경로를 찾는 문제입니다. BFS(너비 우선 탐색)를 사용하여 이 문제를 해결할 수 있습니다. BFS는 주어진 조건 하에서 최소 연산 횟수를 찾는 데 적합한 알고리즘입니다.
문제 해결 방법
- 시작점 A에서 출발하여, 두 가지 연산을 적용하여 가능한 모든 경우의 수를 탐색합니다.
- 각 단계에서의 연산 결과를 큐에 저장하고, 해당 연산이 목표 B와 일치하는지 확인합니다.
- 만약 목표 B와 일치한다면, 해당 단계의 연산 횟수를 반환합니다.
- 큐가 비었는데도 목표 B를 찾지 못했다면, B로 변환할 수 없는 경우이므로 -1을 반환합니다.
알고리즘 설명
- 초기 상태로 A를 큐에 삽입하고, 연산 횟수를 기록합니다.
- 큐에서 요소를 하나씩 꺼내 두 가지 연산을 수행합니다.
- 현재 숫자에 2를 곱한 결과를 큐에 삽입
- 현재 숫자의 가장 오른쪽에 1을 추가한 결과를 큐에 삽입
- 각 연산 결과가 B와 일치하는지 확인합니다.
- 큐가 비어갈때까지 반복하며, 목표 숫자를 찾으면 연산 횟수를 반환합니다.
코드 구현
package AB;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
// 큐를 사용하여 BFS 탐색을 위해 현재 숫자와 연산 횟수를 저장
Queue<long[]> queue = new LinkedList<>();
// 초기 상태로 A와 연산 횟수 1을 큐에 추가
queue.add(new long[]{A, 1}); // 현재 숫자, 연산 횟수
// 큐가 비어있지 않은 동안 반복
while(!queue.isEmpty()){
// 큐의 맨 앞 요소를 꺼내어 현재 상태를 얻음
long[] current = queue.poll();
long num = current[0];
long count = current[1];
// 현재 숫자가 B와 같다면 연산 횟수를 출력하고 프로그램 종료
if(num == B) {
System.out.println(count);
return;
}
// 주의!!
// 아래 if조건 절에서 공통된 `long[] tempArr = new long[2];`를 if 외부에서 선언하고 재활용시 참조 문제를 발생시킨다.
// 연산 1: 2를 곱한다.
boolean condition1 = num * 2 <= B;
if(condition1) {
// 새로운 상태를 저장할 배열 생성
long[] tempArr = new long[2];
tempArr[0] = num*2; // 현재 숫자에 2를 곱한 값을 저장
tempArr[1] = count+1; // 연산 횟수를 1 증가
queue.add(tempArr); // 새로운 상태를 큐에 추가
}
// 연산 2: 1을 수의 가장 오른쪽에 추가한다.
boolean condition2 = num * 10 + 1 <= B;
if(condition2){
// 새로운 상태를 저장할 배열 생성
long[] tempArr = new long[2];
tempArr[0] = num * 10 + 1; // 현재 숫자의 가장 오른쪽에 1을 추가한 값을 저장
tempArr[1] = count + 1; // 연산 횟수를 1 증가
queue.add(tempArr); // 새로운 상태를 큐에 추가
}
}
// 큐가 비었는데도 B를 만들 수 없다면 -1을 출력
System.out.println(-1);
br.close();
}
}
물론입니다! num
이 2인 경우를 가정하여 num * 10 + 1
연산이 어떻게 작동하는지 설명드리겠습니다.
연산 설명
주어진 num
값이 2일 때, 문제에서 주어진 두 가지 연산을 수행할 수 있습니다:
- 2를 곱한다:
num * 2
- 1을 수의 가장 오른쪽에 추가한다:
num * 10 + 1
이제 각각의 연산을 수행해보겠습니다.
연산 1: 2를 곱한다
num = 2
2를 곱한 결과 = 2 * 2 = 4
연산 2: 1을 수의 가장 오른쪽에 추가한다
num = 2
1을 수의 가장 오른쪽에 추가한 결과 = 2 * 10 + 1 = 21
BFS 탐색 과정에서의 동작
BFS 알고리즘을 사용하여 정수 A를 B로 바꾸기 위해 최단 경로를 찾습니다. num
이 2인 경우에 대한 구체적인 예를 살펴보겠습니다.
예를 들어, A가 2이고 B가 162인 경우입니다.
초기 상태:
- 큐:
[(2, 1)]
(초기 숫자와 연산 횟수)
- 큐:
첫 번째 반복:
- 현재 숫자: 2, 연산 횟수: 1
- 가능한 연산 결과:
2 * 2 = 4
2 * 10 + 1 = 21
- 큐에 추가:
[(4, 2), (21, 2)]
두 번째 반복:
- 현재 숫자: 4, 연산 횟수: 2
- 가능한 연산 결과:
4 * 2 = 8
4 * 10 + 1 = 41
- 큐에 추가:
[(21, 2), (8, 3), (41, 3)]
세 번째 반복:
- 현재 숫자: 21, 연산 횟수: 2
- 가능한 연산 결과:
21 * 2 = 42
21 * 10 + 1 = 211
- 큐에 추가:
[(8, 3), (41, 3), (42, 3), (211, 3)]
네 번째 반복:
- 현재 숫자: 8, 연산 횟수: 3
- 가능한 연산 결과:
8 * 2 = 16
8 * 10 + 1 = 81
- 큐에 추가:
[(41, 3), (42, 3), (211, 3), (16, 4), (81, 4)]
다섯 번째 반복:
- 현재 숫자: 41, 연산 횟수: 3
- 가능한 연산 결과:
41 * 2 = 82
(B보다 작으므로 추가)41 * 10 + 1 = 411
(B보다 크므로 추가하지 않음)
- 큐에 추가:
[(42, 3), (211, 3), (16, 4), (81, 4), (82, 4)]
여섯 번째 반복:
- 현재 숫자: 42, 연산 횟수: 3
- 가능한 연산 결과:
42 * 2 = 84
42 * 10 + 1 = 421
- 큐에 추가:
[(211, 3), (16, 4), (81, 4), (82, 4), (84, 4), (421, 4)]
일곱 번째 반복:
- 현재 숫자: 211, 연산 횟수: 3
- 가능한 연산 결과:
211 * 2 = 422
211 * 10 + 1 = 2111
- 큐에 추가하지 않음 (둘 다 B보다 크므로)
여덟 번째 반복:
- 현재 숫자: 16, 연산 횟수: 4
- 가능한 연산 결과:
16 * 2 = 32
16 * 10 + 1 = 161
- 큐에 추가:
[(81, 4), (82, 4), (84, 4), (421, 4), (32, 5), (161, 5)]
아홉 번째 반복:
- 현재 숫자: 81, 연산 횟수: 4
- 가능한 연산 결과:
81 * 2 = 162
(B와 일치)81 * 10 + 1 = 811
(B보다 큼)
- 목표 숫자 B(162)를 찾음, 연산 횟수는 5
결론
num * 10 + 1 <= B
는 현재 숫자num
의 가장 오른쪽에 1을 추가하는 연산을 수학적으로 표현한 것입니다.- 이 조건은 문제에서 주어진 두 가지 연산 중 하나를 구현한 것입니다.
- BFS를 통해 A에서 B로 변환하는 최단 경로를 찾으며, 각 단계에서 가능한 연산 결과가 B를 초과하지 않는지 확인하여 탐색 공간을 줄입니다.
질문
큐에 최초 언제, 어떻게 넣어야 할지 판단 할 수 있을끼?
초기 상태로 A를 큐에 삽입하고, 연산 횟수를 기록합니다.
라고 했다. 여기서 A를 2라고 한다면 별도의 사칙연산을 하기 전 값을
넣어야 하는 근거는 무엇인가?
큐에 최초 값을 넣는 시점은 BFS(너비 우선 탐색) 알고리즘의 시작 부분입니다. BFS는 시작점에서부터 모든 인접한 노드를 탐색하고, 그 다음 레벨의 노드를 탐색하는 방식으로 진행됩니다. 따라서 큐에 최초 값을 넣는 시점은 탐색의 시작점에서 수행되며, 이는 초기 상태를 큐에 삽입하는 것입니다.
최초 값, 2인 A를 2를 곱한다음 넣거나 현재 숫자의 가장 오른쪽에 1을 추가한 결과를 최초 큐에 삽입 하는 것으로 처리 할 수 있는가?
혹은 없는가? 둘다 가능하다면 어떤 것이 더 합리적인 선택인 것인가?
큐에 최초 값을 넣는 시점과 방법
큐에 최초 값을 넣는 시점은 BFS(너비 우선 탐색) 알고리즘의 시작 부분입니다. BFS는 시작점에서부터 모든 인접한 노드를 탐색하고, 그 다음 레벨의 노드를 탐색하는 방식으로 진행됩니다. 따라서 큐에 최초 값을 넣는 시점은 탐색의 시작점에서 수행되며, 이는 초기 상태를 큐에 삽입하는 것입니다.
최초 값의 삽입 방법
초기 상태를 삽입하는 이유
초기 상태, 즉 A의 값을 큐에 넣는 이유는 탐색의 시작점이 되기 때문입니다. A의 값을 큐에 삽입하고, 그 다음 가능한 연산들을 큐에서 처리하여 B로 변환될 수 있는지를 탐색합니다. 이렇게 하는 것이 BFS의 기본적인 흐름에 맞습니다.
최초 값 A를 연산 후 삽입할 수 있는지 여부
최초 값 A를 연산 후 삽입하는 방법도 가능합니다. 하지만 이는 시작점을 변경하는 것과 같으며, BFS 탐색의 구조를 변경하게 됩니다.
두 가지 접근 방식 비교
초기 상태로 A를 큐에 삽입:
- 장점:
- BFS의 구조와 맞으며, 시작점에서부터 모든 가능한 경로를 탐색할 수 있습니다.
- 모든 가능한 연산을 차례로 큐에 삽입하여 탐색하기 때문에, 각 단계에서 최적의 경로를 찾을 수 있습니다.
- 단점:
- 기본적으로 모든 상태를 탐색하기 때문에, 큐에 많은 상태가 삽입될 수 있습니다.
- 장점:
A에 연산을 수행한 후 큐에 삽입:
- 장점:
- 초기 상태에서 가능한 연산을 바로 수행하여 큐에 삽입하면, 탐색 공간이 줄어들 수 있습니다.
- 단점:
- 시작점이 변형되므로 BFS의 기본 구조와 다르게 작동할 수 있습니다.
- 초기 상태에서 바로 연산을 수행하면, 탐색의 깊이가 한 단계 더 깊어질 수 있습니다.
- 장점:
더 합리적인 선택
BFS 탐색에서는 모든 가능한 상태를 차례로 탐색하는 것이 중요합니다. 따라서, 초기 상태로 A를 큐에 삽입하는 것이 더 합리적입니다. 이렇게 하면 탐색의 모든 단계를 순차적으로 거치면서 최적의 경로를 찾을 수 있습니다. 반면, A에 연산을 수행한 후 큐에 삽입하면 탐색의 깊이가 불균형하게 변형될 수 있습니다.
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 한조서열정리하고옴ㅋㅋ - 14659번 (1) | 2024.06.14 |
---|---|
[백준] 거스름돈 - 5585번 (1) | 2024.06.14 |
[백준] 동전 0 - 11047번 (0) | 2024.06.14 |
Greedy 알고리즘 (1) | 2024.06.14 |
[백준] 별자리가될수있다면 - 30821번 (0) | 2024.06.13 |