[BOJ]1463 1만들기🔢 (java,kotlin)

❔문제❔

1463. 1 만들기

🙌Solution(java)🙌

dfs로 풀이(시간 초과)

public class S3_1463_make_one {

    private static int[] res;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder builder = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        res = new int[n + 1];
        int count = dfs(n);

        builder.append(dfs(n));
        System.out.println(builder);
    }

    static int dfs(int n) {

        if (res[n] != 0) return res[n];

        int[] counts = new int[4];
        if (n == 3 || n == 2) return 1;
        if (n % 3 == 0) {
            counts[3] += dfs(n / 3) + 1;
        }
        if (n % 2 == 0) {
            counts[2] += dfs(n / 2) + 1;
        }
        counts[1] += dfs(n - 1) + 1;

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] != 0 && counts[i] < min) min = counts[i];
        }

        res[n] = min;
        return min;
    }
}

처음에 문제를 봤을 때 DFS로 풀면 풀리겠다 싶어서 DFS로 풀었더니 입력값이 50000정도만 되도 stackoverflow가 발생했다.( 최대입력값은 10^6 이었다ㅠㅠ)

DFS로 풀리긴 했어서 접근법이 틀렸다기 보다는 구현방식을 반복문 기반 DFS로 바꾸면 풀리지 않을까 생각이 들었는데 생각보다 직관적이지 않아서 어려웠고 풀면 풀수록 DP구현에 가까워진다는 느낌을 받았다.

다른 사람들은 이걸 어떻게 구현했나 싶어 찾아보니 이 문제가 대표적인 DP문제라고 한다..ㅎ

괜히 이것 때문에 시간 잡아먹고 학습의지도 떨어졌었는데 그냥 좀 일찍 확인할걸 그랬다는 생각이 든다.😂

DP로 풀이

import java.io.*;

public class S3_1463_make_one {

    private static int[] res;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder builder = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        res = new int[n + 1];
        int count = dp(n);

        builder.append(count);
        System.out.println(builder);
    }

    static int dp(int n){

        int[] res=new int[n+1];
        if(n>2) res[3]=1;
        if(n>1)res[2]=1;

        for(int i=4;i<=n;i++){
            int min=Integer.MAX_VALUE;
            if(i%2==0) min=Math.min(res[i/2],min);
            if(i%3==0) min=Math.min(res[i/3],min);
            min=Math.min(res[i-1],min);

            res[i]=min+1;
        }

        return res[n];
    }
}

DP로 푸니까 완전 빨리 풀렸다..

🔠Language Change(kotlin)🔠

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.min

fun main(){
    val br=BufferedReader(InputStreamReader(System.`in`))
    val builder=StringBuilder()

    val n=br.readLine().toInt()
    builder.append(dp(n))
    println(builder)

}

fun dp(n:Int):Int{
    val res=Array(n + 1){0}

    if(n>1) res[2]=1
    if(n>2) res[3]=1

    for(i in 4..n){
        var min=Int.MAX_VALUE
        if(i%3==0) min=min(res[i/3],min)
        if(i%2==0) min=min(res[i/2],min)
        min=min(res[i-1],min)

        res[i]=min+1
    }

    return res[n]

}

🚀Advanced🚀

• 나는 4~n까지 반복을 돌렸는데 res[1]을 정의해서 2~n까지 반복을 돌리며 점화식으로 res[2],res[3]을 정의하는 코드도 있었다.

• 반복문 내부 코드는 아래와 같이 변환해야 더 효율적일 것 같다.

    var min=res[i-1]
    if(i%3==0) min=min(res[i/3],min)
    if(i%2==0) min=min(res[i/2],min)