[백준] S25418

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

25418번: 정수 a를 k로 만들기

 

# 아이디어

처음에 진짜 아무생각이 안 났다.

그래서 그냥 밑에 보니까 BFS라고 적혀 있어서 기계처럼 BFS 만들기만 함.

모든 노드를 생성하여 결과값이 나올 때 종료하자!

=> 연산 횟수가 너무 많아진다.

 

Sol1.

메모리 초과도 발생하면서 올바른 결과값이 안나온다..

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static int k;

    public static int bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        ArrayList<Integer> exist = new ArrayList<>();
        queue.offer(start);

        int stage = start;
        int cnt = 0;
        while (!queue.isEmpty()) {
            int last = (int) queue.poll();
            exist.add(last);

            queue.offer(last + 1);
            queue.offer(last * 2);

            if (last != start && stage + 1 == last && !exist.contains(last /2)) {
                cnt++;
                stage++;
            }

            if (last == k)
                return cnt;
        }

        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        k = sc.nextInt();

        System.out.println(bfs(n));

        sc.close();

    }

}

 

# 오답 & 블로그

모든 노드 그리면서 큐에 담으니까 메모리 초과가 발생함.. 찾아보니 시간 초과도 발생한다네..

결과적으로 연산 횟수를 줄여야 한다!!!

 

방법 1. 방문 여부를 활용하여 Memorization을 한다.

방법 2. 거꾸로 결과값에서 나누기 2가 가능한지 아닌지 판별하여 시작값으로 돌아온다.

 

방법 1은 아직 이해가 잘 안 간다... DP를 공부해보고 다시 돌아오겠다 ㅠㅠ

방법 2는 그리디 탐욕법이라고 한다더라. 2로 나눌 수 있으면 나누고, 못 나누면 1빼기

 

Sol2. 등호를 안 붙여서 2에서 5가 되는 경우 연산이 3번 필요하게 되었다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        int cnt = 0;
        int temp = k;
        while (temp != n) {
            if (temp % 2 == 0 && temp / 2 > n) {
                temp /= 2;
            } else {
                temp -= 1;
            }
            cnt++;
        }

        System.out.println(cnt);

        sc.close();

    }

}

 

Sol3. 끄읕

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        int cnt = 0;
        int temp = k;
        while (temp != n) {
            if (temp % 2 == 0 && temp / 2 >= n) {
                temp /= 2;
            } else {
                temp -= 1;
            }

            cnt++;
        }

        System.out.println(cnt);

        sc.close();

    }

}

 

 

💯💯💯

언제 1을 더하고 2를 곱할지 결정해야 하는지를 고민하느라

연산횟수를 줄이기 위해서는 최대한 많은 나눗셈이 필요하다는 사실을 망각했다는 점...

실망스럽다 :(