728x90
🤔 문제 접근
+1, -1, *2 연산만을 이용해 n이 k가 될 때 까지의 최소 비용을 구하는 문제이다.
*2는 -1,+1과 달리 순간이동이기 때문에 시간이 소요되지 않는 것에 유의해야 한다.
Info 클래스를 생성하여 위치와 시간을 저장하도록 했다.
🚨CODE
import java.util.*;
import java.io.*;
/*
* 구해야하는 것 : n에서 k까지의 최단 시간
* 움직일 수 있는 방법 : 현재 위치에서 -1, +1, *2
* 만약 도착지점을 초과한 경우 뒤로 가야하며 이때는 -1 연산밖에 없음 앞으로가는 것은 +1, *2
* +1, -1은 1초가 소요되나 *2는 0초가 소요된다.
*/
public class Main {
static int max = 100000;
static int min = Integer.MAX_VALUE;
static boolean[] visit = new boolean[max+1];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
Queue<Info> q = new LinkedList<>();
q.offer(new Info(n, 0));
while(!q.isEmpty()) {
Info info = q.poll();
int pos = info.pos;
int time = info.time;
visit[pos] = true;
if(pos == k) {
min = Math.min(min, time);
}
if(pos*2 <= max && !visit[pos*2]) {
q.offer(new Info(pos*2, time));
}
if(pos+1 <= max && !visit[pos+1]) {
q.offer(new Info(pos+1, time+1));
}
if(pos-1 >= 0 && !visit[pos-1]) {
q.offer(new Info(pos-1, time+1));
}
}
System.out.println(min);
}
}
class Info{
int time; // 현재까지 걸린 시간
int pos; // 현재 위치
Info(int curPos, int curTime){
this.time = curTime;
this.pos = curPos;
}
}
728x90
반응형
'코딩테스트' 카테고리의 다른 글
[SQL] 프로그래머스 - 3월에 태어난 여성 회원 목록 출력하기 (0) | 2024.02.20 |
---|---|
[SQL] 프로그래머스 - 12세 이하인 여자 환자 목록 출력하기 (0) | 2024.02.20 |
[JAVA] 백준 20207 - 달력 (0) | 2024.02.18 |
[JAVA] 백준 2615 - 오목 (1) | 2024.02.17 |
[JAVA] 백준 - 2023 신기한 소수 (0) | 2024.02.14 |