문제 파악
https://www.acmicpc.net/problem/16953
접근 방법
bfs를 통해 접근하면 어떨까?
- 2를 곱하는 경우
- 1을 을 수의 가장 오른쪽에 추가하는 경우
- 두 가지의 경우의 수를 큐에 넣어 준 다음, 만약 a가 b와 같게 된다면 answer를 갱신하고, 반복문을 종료하였다.
- 무한 루프의 반복을 막기 위해, 다음 수가 b값을 넘지 않는 조건에서만 큐에 다음 수를 넣어주었다.
코드 구현
첫번째 코드(틀린 코드)
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
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());
int answer = Integer.MAX_VALUE;
Deque<int[]> q = new ArrayDeque<>();
q.offerLast(new int[]{a,0});
while(!q.isEmpty()){
int [] curr = q.pollFirst();
int curr_a = curr[0];
int count = curr[1];
if(curr_a == b){
answer = Math.min(answer, count);
}
if(curr_a * 2 <= b){
q.offerLast(new int[]{curr_a*2,count+1});
}
if(curr_a*10 + 1 <= b){
q.offerLast(new int[]{curr_a*10+1,count+1});
}
}
if(answer == Integer.MAX_VALUE){
System.out.println(-1);
}else{
System.out.println(answer+1);
}
}
}
정답코드
import java.util.*;
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long a = Long.parseLong(st.nextToken()); // long 자료형으로 변경
long b = Long.parseLong(st.nextToken());
int answer = -1;
Deque<long[]> q = new ArrayDeque<>(); // 큐에서 long[] 사용
q.offerLast(new long[]{a, 1});
while (!q.isEmpty()) {
long[] curr = q.pollFirst();
long curr_a = curr[0];
int count = (int) curr[1];
if (curr_a == b) {
answer = count;
break;
}
if (curr_a * 2 <= b) {
q.offerLast(new long[]{curr_a * 2, count + 1});
}
if (curr_a * 10 + 1 <= b) {
q.offerLast(new long[]{curr_a * 10 + 1, count + 1});
}
}
System.out.println(answer);
}
}
→ 처음 코드가 4%에서 자꾸 오류가 나 int형을 long형으로 모두 바꾸어주었다 !
문제에서 발생하는 두 가지의 연산 중,
(1) A * 2
최대값: A×2≤2×109=2,000,000,000, int 범위 (2,147,483,647)를 초과하지 않으므로,
A * 2는 int로 충분히 처리 가능 !
(2) A * 10 + 1 (오버플로우 발생)
최대값: A×10+1≤10×109+1=10,000,000,001, int 범위 (2,147,483,647)를 초과하므로, long이 필요
자료형을 틀리신 다른 분들을 위한 테스트셋
500000000 705032705
잘못된 출력 값: 2
답: -1
다른 사람 코드
import java.io.*;
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());
long A = Long.parseLong(st.nextToken());
long B = Long.parseLong(st.nextToken());
int count = 1; // 이미 B가 초기 상태이므로 연산 횟수를 1부터 시작
while (B > A) {
// 1) B가 10으로 끝나는 수(일의 자리가 1)이면 (B-1)/10
if (B % 10 == 1) {
B = (B - 1) / 10;
count++;
}
// 2) B가 짝수이면 B /= 2
else if (B % 2 == 0) {
B /= 2;
count++;
}
// 3) 그 외에는 더 이상 줄일 수 없으므로 break
else {
break;
}
}
// 최종적으로 B == A면 count를, 아니면 -1을 출력
System.out.println((B == A) ? count : -1);
}
}
업다운 방식으로 푸니 깔끔 그 자체가 되었다 ….
배우게 된 점
입력 값의 범위를 꼼꼼히 살펴볼 것 ! 🐸
'[Algorithm] 알고리즘' 카테고리의 다른 글
| [백준][boj] RGB거리 2(17404) - JAVA (1) | 2025.06.06 |
|---|---|
| [백준][boj] 멀티탭 스케줄링(1700) - JAVA (1) | 2025.01.13 |
| [백준][boj]N과 M(5) - JAVA (0) | 2025.01.10 |
| [프로그래머스][JAVA] 조이스틱 - 그리디 (1) | 2025.01.06 |
| [프로그래머스] 체육복 (JAVA) (1) | 2024.12.27 |