[백준 1463번/JAVA] 1로 만들기

문제

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

1463번: 1로 만들기

 

풀이1

dp문제 푸는 법을 여러 개 익힌 후 2xn타일링 2xn 타일링 2 타일링 퇴사 풀어본 문제다.

dp는 규칙 찾기 -> 점화식 세우기 -> 함수로 구현 순서로 풀어야 한다.

 

문제를 접하고 처음 풀어낸 방법 :

1. 먼저 규칙을 찾기 위해 1이 되기 위해 필요한 최소 연산 횟수를 하나 하나 구해보았다.
2. N/3 N/2 N-1 중 하나를 써서 이미 구해진 결과 중 가장 작은 횟수에 해당되는 수로 만들어야 한다는 것을 생각해냈다.
3. 숫자가 3의 배수라면 무조건 3으로 먼저 나눠야 연산 횟수를 크게 줄일 수 있으니, 3의 배수인 경우와 3의 배수가 아닌 경우로 나누어보았다.
4. 3의 배수면 3으로 나눈 값을 재귀호출(값이 저장되어있다면 그 값 리턴)
5. 3의 배수가 아니면? 3의 배수가 될 때까지 -1하기..? 2로 나누기? 여기서 막혔다.
6. 3의 배수가 아니면 N-1, N-2 중 더 작은 연산횟수를 가진 값을 선택한다. -> 여기서 '여러 경우 중 적은 값을 선택'하는 아이디어를 떠올림
7. 경우의 수를 더 나누었다. 3배수도 2배수도 아닌 경우, 3배수인 경우, 2배수인 경우, 3배수와 2배수 모두 해당되는 경우.
8. 3배수도 2배수도 아닌 경우 : d[N-1] + 1
9. 3배수인 경우 : d[N/3]
10. 2배수인 경우 : Math.min(d[N-1] +1 , d[N/2] + 1)
11. 3배수이면서 2배수인 경우 : d[N/3]
12. dp(N) = dp(N-1) + 1 + dp(N/2) + 1 + dp(N/3) + 1으로 점화식을 세워보기도 했지만 직접 작은 수를 대입해보니 정답이 나오지 않았다. 그래서 이전에 생각한 것처럼 조건문을 나눠야겠다고 생각했다.

여기까지 생각하고 내 생각과 비교하기 위해 다른 풀이를 찾아보았다.
경우의 수를 나누는 방법은 같았지만 최솟값을 구하는 방법이 틀렸다.

3의 배수인 경우 : Math.min(d[N-1] +1 , d[N/3] + 1)
2의 배수인 경우 : Math.min(d[N-1] +1 , d[N/2] + 1)
6의 배수인 경우 : Math.min(d[N-1] +1 , Math.min(d[N/3] + 1, d[N/2] + 1)) (Math.min()은 인자 두 개만 비교 가능)
모두 아닌 경우 : d[N-1] + 1

 

힌트에서 N이 2의 배수일 때 N-1과 N/2 중 더 작은 값을 골라야 하는 것을 알 수 있었다.
마찬가지로 N이 3의 배수일 때도 N-1과 N/3을 비교해서 최솟값을 구해야 한다.
N이 6의 배수일 때도 마찬가지다.

코드1

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static int[] d;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        d = new int[N+1];
        System.out.println(dp(N));
    }
    static int dp(int x){
        if(x == 1) return 0;
        if(x == 2) return 1;
        if(x == 3) return 1;
        if(d[x] != 0) return d[x];
        if(x%3==0 && x%2==0) return d[x] = Math.min(Math.min(dp(x/3), dp(x/2)), dp(x-1))+1;
        else if(x%3 == 0) return d[x] = Math.min(dp(x/3), dp(x-1)) + 1;
        else if(x%2 == 0) return d[x] = Math.min(dp(x/2), dp(x-1)) + 1;
        else return d[x] = dp(x-1) + 1;

    }
}

 

 

풀이2

2024-08-15 다시 풀이

 

골드3 dp문제( 1082번: 방 번호 (acmicpc.net) )를 풀다가 난이도가 쉬운 편인 이 문제를 예시로 든 설명이 있어서 다시 풀어보았다.

난이도 높은 문제를 여럿 풀다가 다시 이 문제를 풀다보니 확실히 문제 풀이 흡수력이 높아진 느낌이다. 

이전에는 왜 이렇게 풀어야 하는지 완전히 이해되지 않은 채 풀이를 쓰고 끝냈다면 지금은 혼자서 어느 정도 접근 방법을 떠올릴 수 있게 되었다. 

 

먼저 brute-force로 1이 될 때까지 세 방법을 모두 쓰도록 반복해서 최소 연산 횟수를 출력하는 방법을 떠올렸다.

 

 * 참고 : 연산 횟수가 최소여야 하니까 세 방법 중 연산 결과가 가장 작은 연산을 선택하면 되지 않을까? 라고 생각할 수도 있지만, 이 방법은 잘못됐다. 힌트에도 ' 10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다. ' 라고 나와있듯이, 10의 경우 연산 결과가 가장 작은 경우만 선택해가다보면 10 -> 5 -> 4 -> 2 -> 1 로 4번 만에 1을 만들 수 있다는 오답이 도출된다. 

//잘못된 코드
static int toOne(int N){
        if(N == 1)
            return 0;

        int ret = N;

        if(N%3 == 0){
            ret = Math.min(ret, toOne(N/3));
        }
        if(N%2 == 0){
            ret = Math.min(ret, toOne(N/2));
        }
        ret = Math.min(ret, toOne(N-1));

        return ret;
    }

 

 

이처럼 brute-force로 구현하면 시간 초과가 발생한다.

import java.io.*;
import java.util.*;

public class boj_1082 {
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        toOne(N, 0);
        bw.write(ans + " ");
        bw.close();

    }
    static void toOne(int N, int count){
        if(N == 1){
            ans = Math.min(ans, count);
            return;
        }
        
        if(N%3 == 0){
            toOne(N/3, count+1);
        }
        if(N%2 == 0){
            toOne(N/2, count+1);
        }
        toOne(N-1, count+1);
    }
}

 

코드2

앞서 짠 코드는 매 연산마다 N/3, N/2, N-1을 일일이 해서 뻗어나간 모든 가지의 연산 횟수를 세고, 최소 연산 횟수를 찾는 방법이었다. 그러나 이 방법은 재귀 호출이 잦아 시간 초과가 발생하였다.

 

단순히 똑같은 인자가 또 들어오는 경우 기존에 계산했던 값을 반환하도록 메모이제이션 기법을 추가해보자.

 

매 연산마다 N/3, N/2, N-1을 일일이 하되, 재귀 호출 과정에서 이미 최소 연산 횟수를 구한 경우 그 값을 그대로 출력하도록 했다.

 

먼저 최소 연산 횟수를 저장할 dp를 선언한다. dp의 크기는 문제에서 제시한 입력값이 충분히 담길 만큼의 크기로 선언해야 한다. N이 최대 10^6이 될 수 있으므로 크기를 1000001으로 선언했다.

 

dp에는 N/3, N/2, N-1에 의해 뻗어나간 여러 가지 중 '최소'연산 횟수를 저장해야 하므로 Math.min()를 이용해 값을 채웠다. 

비교 결과 더 작은 값을 구해야 하므로 dp의 초기값을 Integer.MAXVALUE로 설정했다.

 

toOne()함수에 N이 들어오면 dp에 N의 최소 연산 횟수를 저장한다. 

dp[N] = Math.min( dp[N], toOne(N/3)+1 ) 

현재 dp[N]값과 dp[N/3] + 1 즉 'N/3의 최소 연산 횟수 + 1' 을 비교해서 더 작은 값으로 dp[N]을 업데이트한다.

N/2, N-1도 마찬가지로 진행하면 세 연산 중 가장 연산 횟수가 작은 값이 dp[N]에 저장된다.

 

마지막으로 dp[N]에 채워진 값을 출력하면 된다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        dp = new int[1000001];
        Arrays.fill(dp, Integer.MAX_VALUE); //dp의 모든 값을 -1로 초기화
        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 1;

        toOne(N);

        bw.write(dp[N] + " ");
        bw.close();

    }
    static int toOne(int N){
        //dp[]에 각 숫자에 해당하는 최소 연산 횟수를 저장

        if(dp[N] != Integer.MAX_VALUE) return dp[N]; //이미 구해진 값이 있다면 그 값을 리턴

        if(N%3 == 0){
            dp[N] = Math.min(dp[N], toOne(N/3) + 1);
        }
        if(N%2 == 0){
            dp[N] = Math.min(dp[N], toOne(N/2) + 1);
        }
        dp[N] = Math.min(dp[N], toOne(N-1) + 1);

        return dp[N];
    }
}