• Home

My Codegate

  • Home

백준 25418 정수 a를 k로 만들기 자바 문제풀이

2024/01/11 Posted by Codegate Java No Comments
백준 25418  정수 a를 k로 만들기 자바 문제풀이

문제 링크

문제 내용은 입력으로 두 수를 받아 왼쪽 수에 +1과 *2를 사용해서 오른쪽 수를 만들 경우, 최소 연산 횟수는 몇번인지를 출력하는 것인데 만들지 못하는 경우는 주어지지 않는다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

// 정수 a를 k로 만들기 https://www.acmicpc.net/problem/25418
public class AtoK {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int[] split = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{split[0], 0});

    int ans = 0;
    boolean[] visited = new boolean[split[1] + 1];
    while (!queue.isEmpty()) {
      int[] poll = queue.poll();
      visited[poll[0]] = true;
      if (poll[0] == split[1]) {
        ans = poll[1];
        break;
      }

      if (poll[0] * 2 < visited.length) {
        if (!visited[poll[0] * 2]) {
          queue.add(new int[]{poll[0] * 2, poll[1] + 1});
        }
      }

      if (poll[0] + 1 < visited.length) {
        if (!visited[poll[0] + 1]) {
          queue.add(new int[]{poll[0] + 1, poll[1] + 1});
        }
      }
    }
    System.out.println(ans);
  }

}

문제 내용을 보면 단순 계산으로 접근할 경우 1111 가지고 997651 구하느라 무한한 시간을 허비해야 하는데, visited 배열과 BFS를 사용해주면 문제를 무한한 시간 허비 없이 해결할 수 있는데

boolean 타입의 visited 배열을 목표값보다 + 1이 더 큰 크기로 생성한 후, Queue에 시작 값과 0을 배열 형태로 넣어준 후 Queue를 돌려주면서 현재 값을 visited 처리해주고, * 2와 +1을 해주면서 횟수를 증가시키면서 진행하되, 이미 방문한 값에는 또 방문하지 않게 해주고

Queue에서 값을 뽑을 때마다, 뽑은 값이 목표 값과 같다면 바로 Queue를 중단해주면서, 시도 횟수를 출력해주면 끝이다

No Comments
0

Leave a Reply Cancel Reply

Introduction

My Codegate

Latest Posts

  • Google Search Console API 연동방법
  • 인텔리제이 Gradle Dependency 최신 버전 보는 방법
  • Wallet-Tracker 개발일지
  • Moralis API 자바로 호출방법
  • IntelliJ Commit 후 Push 따로 하는 방법

Categories

  • My Project (4)
  • Java (42)
  • Algorithm (161)
    • Java (152)
    • Algorithm Knowledge (3)
    • Algorithm site usage (6)
  • Vue.js (1)
  • Spring (4)
  • Docker (2)
  • IntelliJ (20)
  • Uncategorized (7)

Recent Comments

  • Codegate on Hello world!
  • A WordPress Commenter on Hello world!

© 2025 — mycodegate.com

Prev Next