이번에 풀어본 문제는
백준 12852번 1로 만들기 2 입니다.

📕 문제 링크

❗️코드

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

class One
{
    int n,cnt;
    String str;

    public One(int n, int cnt, String str) {
        this.n = n;
        this.cnt = cnt;
        this.str = str;
    }

    public String add(int n)
    {
        return this.str+" "+n;
    }
}
public class Main {
    static int N;
    static boolean [] visited;
    static Queue<One> q;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        visited = new boolean[N];

        q = new LinkedList<>();
        q.add(new One(N,0,N+""));

        StringBuilder sb = new StringBuilder();
        while(!q.isEmpty())
        {
            One cur = q.poll();

            if(cur.n == 1)
            {
                sb.append(cur.cnt).append("\n").append(cur.str);
                break;
            }
            //3나누기
            if((cur.n % 3) == 0) calc(cur,0);
            //2나누기
            if((cur.n % 2) == 0) calc(cur,1);
            //빼기
            calc(cur,2);
        }
        System.out.print(sb);
    }
    static void calc(One cur, int idx)
    {
        int next;
        if(idx == 0) next = cur.n / 3;
        else if(idx == 1) next = cur.n / 2;
        else next = cur.n-1;
        if(!visited[next])
        {
            visited[next] = true;
            q.add(new One(next,cur.cnt+1,cur.add(next)));
        }
    }
}

📝 풀이

3가지 연산을 활용하여 주어진 N값을 최소한의 연산횟수로 1로 만드는 방법을 구하는 문제입니다.
먼저 큐에 시작값인 N을 담고, 나누기 조건에 맞추어 calc함수로 현재 숫자와 카운트를 전달합니다. 방문 배열을 활용하여 현재 시점보다 늦은 시점에 도달한 연산을 제외시켜주고, 목푯값인 1을 만들었다면 큐를 벗어나 진행 과정을 출력하기 위해 쌓아둔 str값과 횟수를 출력해주면 해결할 수 있습니다.

📜 후기

이번 코딩테스트에서 dp에 크게 데여서.. 부족한 부분을 보완하고자 dp문제를 선택했습니다. 그런데 읽어보니 bfs 풀이가 저에게 더 잘 맞을 것 같아서 bfs로 구현해보았습니다.