[Java] Boj 25418: 정수 a를 k로 만들기

2025. 7. 7. 19:43·PS/Solve

문제

https://www.acmicpc.net/problem/25418

 

풀이

 문제를 간단히 요약하면 입력받은 정수 값 A에 두 가지 연산을 적용해 정수 K로 만드는 것이다. 연산 1은 정수 A에 1을 더하기, 연산 2는 정수 A를 2로 곱하기이다. 처음에는 문제 해결을 위한 아이디어를 다음과 같이 잡았다. 먼저 방문 여부를 체크할 visit 배열과 해당 인덱스까지 몇 번만에 도달할 수 있는지를 저장할 arr를 선언한다. 이후 bfs 메소드를 만들어 인자로 정수 n을 받아, arr[n * 2]가 방문하지 않은 상태라면 arr[n] + 1의 값을 저장한다. 그리고 n * 2에 bfs를 다시 걸어 n * 2를 기준으로 bfs를 또 실행한다. 마찬가지로 arr[n+1]이 방문하지 않은 상태라면 arr[n] + 1의 값을 저장하고 방문 처리를 하고, n + 1에도 bfs를 또 실행한다. 그런데 너무 오랜만에 PS를 하니 이게 DFS인지도 모르고 무작정 예제 입력을 넣으니 스택 오버플로우가 터졌다. 그래서 BFS를 구현한 방식을 최대한 떠올려 간신히 큐를 이용해 BFS를 구현한걸 기억해내서 아래와 같이 큐를 이용해 구현하였다.

 

따라서 다음과 같이 구현을 하였다.

 

코드

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
    public static Queue<Temp> q;
    public static boolean[] visit;
    public static int k;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        q = new LinkedList<>();
        int n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        visit = new boolean[k+1];
        q.add(new Temp(n, 0));
        visit[n] = true;
        while (! q.isEmpty()) {
            Temp t = q.poll();
            int idx = t.n;
            int cnt = t.count;
            if (idx == k) { System.out.println(cnt); break; }
 
            if (idx * 2 <= k && !visit[idx * 2]) {
                q.add(new Temp(idx * 2, cnt + 1));
                visit[idx * 2] = true;
            }
            if (idx + 1 <= k && !visit[idx + 1]) {
                q.add(new Temp(idx + 1, cnt + 1));
                visit[idx + 1] = true;
            }
        }
    }
 
    public static class Temp {
        int n;
        int count;
        public Temp(int n, int count) {
            this.n = n;
            this.count = count;
        }
    }
}
 
Colored by Color Scripter
cs

 

 코드를 살짝 뜯어보자. 문제에서 제공되는 A는 그냥 n으로 사용하였다. Temp 클래스는 인덱스로 사용할 n과 n까지 도달 가능한 횟수를 저장하는 count 필드를 가진다. 입력 값 n까지는 바로 도달할 수 있으니 count를 0으로 하여 큐에 넣어준다. 이제 while 반복문을 통해 bfs를 구현했는데 큐에서 하나 뺀 뒤에 n의 값을 먼저 확인한다. 뺐는데 인덱스가 k라면 이미 도착한거니 도달하는 횟수인 cnt를 출력하고 break를 걸어주면 된다. 만약 아니라면, 위의 두 연산을 차례로 진행해서 큐에 넣어주면 된다. 큐에 넣어줄 때에도 n에 2를 곱한 값 / n + 1에 이미 도착하였는지 체크를 하고 넣어준다. 이제 이 탐색을 큐가 빈 상태까지 반복해주면 된다. 큐가 빌 때까지 반복을 하여도 어차피 n이 k 값이 되면 중간의 if 구문을 통해 종료되므로 상관이 없다.

'PS > Solve' 카테고리의 다른 글

[Java] Boj 14496: 그대, 그머가 되어  (2) 2025.07.11
[Java] Boj 6528: 106 miles to Chicago  (0) 2025.03.13
[Java] Boj 24052: 알고리즘 수업 - 삽입 정렬 2  (0) 2025.03.11
[Java] Boj 24051: 알고리즘 수업 - 삽입 정렬 1  (0) 2025.03.11
[Java] Boj 23882: 알고리즘 수업 - 선택 정렬 2  (0) 2025.03.11
'PS/Solve' 카테고리의 다른 글
  • [Java] Boj 14496: 그대, 그머가 되어
  • [Java] Boj 6528: 106 miles to Chicago
  • [Java] Boj 24052: 알고리즘 수업 - 삽입 정렬 2
  • [Java] Boj 24051: 알고리즘 수업 - 삽입 정렬 1
hyeon0117
hyeon0117
컴공으로 살아남기
  • hyeon0117
    컴공 생활기
    hyeon0117
  • 전체
    오늘
    어제
    • 분류 전체보기 (55) N
      • Algorithm (2)
      • PS (17) N
        • Solve (17) N
      • CS (36)
        • 객체지향설계 & 패턴 (12)
        • COLMAP (2)
        • 머신러닝 (1)
        • 프로그래밍 언어론 (19)
        • 형식언어 (1)
        • 운영체제 (1)
  • 블로그 메뉴

    • 홈
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    PS
    자료형
    선택 정렬
    블록 구조 언어
    플로이드 - 워셜
    다이나믹 프로그래밍
    객체지향언어
    최단 경로
    백준23882
    형식언어
    객체지향설계
    자료구조
    PLT
    함수
    디자인 패턴
    java
    BOJ
    soild 패턴
    언어 타입
    백준 6825
    의미론
    어휘 분석기
    디자인패턴
    백준13417
    백준 25418
    알고리즘
    객체지향
    백준
    프로그래밍 언어론
    형식언어론
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
hyeon0117
[Java] Boj 25418: 정수 a를 k로 만들기
상단으로

티스토리툴바