(JAVA) 백준 문제 풀이 - 동적계획법 단계 - 1463번 1로 만들기 (실버3)

JAVA/코딩 테스트

(JAVA) 백준 문제 풀이 - 동적계획법 단계 - 1463번 1로 만들기 (실버3)

VarcharC2K 2023. 10. 27. 22:53

주어진 수를 규칙에 따라 1로 만들 때 가장 최소 연산하는 횟수를 구하는 간단한 문제이다.

정말 간단한 문제였는데 생각을 잘못해서 한참을 헤멘 문제이기도 했다.

그럼 문제를 한번 살펴보자.

정말 간단한 문제!

문제는 정말 간단하다.

우선 규칙은

3으로 떨어지면 3으로 나누거나
2로 떨어지면 2로 나누거나
1을 뺀다.

이다.

즉, 주어진 수 크기의 배열을 만들고, 최소값만 가져오면 마지막 주어진 수 n 에는 최소 횟수가 기록되게 된다.

다만, 주의 할점이 있는데 예를 들어 10의 경우 2로 나눌수 있기 때문에 바로 2로 나누는 경우 10 > 5 > 4 > 2 > 1의

4번이 되지만 -1을 하면 10 > 9 > 3 > 1 이되므로 3번만에 나눌수 있다.

그렇다면 우리가 비교할 것은 지금 수에 -1 한 값과 나눌 값중 작은 값을 가져오면 되는 것이다,

그럼 규칙을 한번 다시 정리해 보자.

3으로 나누어 떨어지는 경우 -1한 인덱스의 값과 3으로 나눈 인덱스의 값 중 작은 것에 1을 더한다. (자기 자신을 해당 인덱스로 바꾸는 연산이 +1회 되므로)
2로 나누어 떨어지는 경우 -1한 인덱스 값과 2로 나눈 인덱스의 값 중 작은 것에 1을 더한다.
그 외에 경우 -1 한 인덱스의 값에 1을 더한다.

그럼 끝난 것이냐?

아니다, 추가적으로 생각할 것이 하나 남았다.

3과 2로 둘다 나누어 지는 경우, 어느 것이 더 작은 값인지 한번 더 확인을 해야한다.

3과 2로 둘다 나누어지는 경우는 6으로 나누어 떨어지는 경우와 같으므로 마지막 규칙이 하나 추가 된다.

3으로 나누어 떨어지는 경우 -1한 인덱스의 값과 3으로 나눈 인덱스의 값 중 작은 것에 1을 더한다. (자기 자신을 해당 인덱스로 바꾸는 연산이 +1회 되므로)
2로 나누어 떨어지는 경우 -1한 인덱스 값과 2로 나눈 인덱스의 값 중 작은 것에 1을 더한다.
그 외에 경우 -1 한 인덱스의 값에 1을 더한다.
6으로 나누어 떨어지는 경우 -1한 인덱스의 값, 3으로 나눈 인덱스의 값, 2로 나눈 인덱스의 값 중 작은 것에 1을 더한다.

그럼 모든 경우의 수가 갖추어 졌으니 문제를 풀어보자.

항상 에지 케이스와 순서를 생각해 보자...

import javax.print.attribute.standard.PresentationDirection;
import java.io.*;
import java.util.*;

class Main{
    public static int n;

    public static Integer[] dp;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new Integer[n+1];
        if (n > 3) {
            for (int i = 0; i <= 3; i++) {

                dp[i] = 1;
            }
            System.out.println(recur(n));
        } else {
            System.out.println(1);
        }
    }

    public static int recur(int n) {
        if (dp[n] == null) {
            if(n % 6 == 0){
                dp[n] = Math.min(recur(n - 1), Math.min(recur(n / 3), recur(n / 2))) + 1;
            } else if (n % 3 == 0) {
                dp[n] = Math.min(recur(n - 1), recur(n / 3)) + 1;
            } else if (n % 2 == 0) {
                dp[n] = Math.min(recur(n - 1), recur(n / 2)) + 1;
            } else {
                dp[n] = recur(n - 1) + 1;
            }
        }
        return dp[n];
    }
}

나는 처음에 위와 같이 구현하였다.

주어진 수보다 +1만큼의 배열을 선언하고(해당 숫자가 나오기 위해서 +1을 해준다) 3보다 작은 경우 초기값 1을 넣어주고, 아닌경우 1을 출력한다.

그리고 짜여진 규칙대로 -1한 값과 나눈 값중 더 적은 것을 Memoization 한 후 리턴한다.

그러면 최종적으로 가장 작은 횟수를 구할 수 있을 것이라고 생각했다.

그런데 실제로 제출해보니 시간 초과가 발생했다.

효율성을 높이기 위해 동적계획법을 사용하는 것인데 시간 초과라니?

분명 규칙 상에 문제는 없어 보였는데, 우선은 호출 스택에 문제가 발생하는 것이라 생각하여 위 코드를 Top-Down 방식에서 Bottom-Up 방식으로 변경해 보았다.

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

class Main{
    public static int n;
    public static Integer[] dp;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new Integer[n+1];
        if (n > 3) {
            for (int i = 0; i <= 3; i++) {

                dp[i] = 1;
            }
            System.out.println(recur(n));
        } else {
            System.out.println(1);
        }
    }

    public static int recur(int n) {
        if (dp[n] == null) {
            for (int i = 4; i <= n; i++) {
                if (i % 6 == 0) {
                    dp[i] = Math.min(dp[i / 2], dp[i / 3]) + 1;
                } else if (i % 3 == 0) {
                    dp[i] = Math.min(dp[i - 1], dp[i / 3]) + 1;
                } else if (i % 2 == 0) {
                    dp[i] = Math.min(dp[i - 1], dp[i / 2]) + 1;
                } else {
                    dp[i] = dp[i - 1] + 1;
                }
            }
        }
        return dp[n];
    }
}

제출을 해보니 잘 굴러가길래 Top-Down만 안되는 경우인건가 생각했는데 이번엔 99%에서 틀렸다는 답변을 돌려받았다.

여기서 부터 머리가 복잡해지기 시작했다.

아무리 생각해도 예외 케이스를 모르겠는것...

ChatGPT도 돌려보고 다른 사람의 코드도 보고 했는데 다들 나랑 똑같이 짰는데? 라고 생각했는데 알고보니 정말 간단한 실수였다.

주어진 문제의 제약조건은 1~ 100,000까지였는데 1을 넣을때 0이 아니라 1로 출력을 한 것!

다시 생각해봐도 정말 바보같은 실수가 아닌가 싶다...

최종적으로 코드를 수정하니 정답처리를 받을 수 있었다.

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

class Main{
    public static int n;
    public static Integer[] dp;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new Integer[n+1];
        if (n > 3) {
            for (int i = 0; i <= 3; i++) {

                dp[i] = 1;
            }
            System.out.println(recur(n));
        } else {
            if(n == 1){
                System.out.println(0);
            } else{
                System.out.println(1);
            }
            
        }
    }

    public static int recur(int n) {
        if (dp[n] == null) {
            for (int i = 4; i <= n; i++) {
                if (i % 6 == 0) {
                    dp[i] = Math.min(dp[i / 2], dp[i / 3]) + 1;
                } else if (i % 3 == 0) {
                    dp[i] = Math.min(dp[i - 1], dp[i / 3]) + 1;
                } else if (i % 2 == 0) {
                    dp[i] = Math.min(dp[i - 1], dp[i / 2]) + 1;
                } else {
                    dp[i] = dp[i - 1] + 1;
                }
            }
        }
        return dp[n];
    }
}

그럼 또다시 궁금한 점이 생겼는데, 다른 사람의 코드를 보다가 Top-Down 방식으로도 구현한 사람들이 많다는 것을 발견했다.

그럼 내 코드는 무엇이 문제이길래 시간 초과가 나는 것일까?

코드를 계속 비교해 보다가 이유를 알았는데, 재귀 호출시 호출하는 순서가 문제였다.

  if (dp[n] == null) {
            if(n % 6 == 0){
                dp[n] = Math.min(recur(n - 1), Math.min(recur(n / 3), recur(n / 2))) + 1;
            } else if (n % 3 == 0) {
                dp[n] = Math.min(recur(n - 1), recur(n / 3)) + 1;
            } else if (n % 2 == 0) {
                dp[n] = Math.min(recur(n - 1), recur(n / 2)) + 1;
            } else {
                dp[n] = recur(n - 1) + 1;
            }
        }

재귀 호출부의 코드를 살펴보자.

나는 코드의 가장 처음에 recur(n -1)로 -1부터 호출을 하게 해두었다.

Top-Down 방식은 최대값 부터 아래로 내려가는 방식인데 -1부터 계산하게 되니 사실상 던지는 숫자 만큼 재귀호출을 하는것!

이러니 효율이 나올리가 없었다.

결과적으로 순서를 바꿔주니 정답을 얻을 수 있었다.

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

class Main{
    public static int n;

    public static Integer[] dp;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new Integer[n+1];
        dp[0] = dp[1] = 0;

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

    }

    public static int recur(int n) {
        if (dp[n] == null) {
            if(n % 6 == 0){
                dp[n] = Math.min(Math.min(recur(n / 3), recur(n / 2)),recur(n - 1)) + 1;
            } else if (n % 3 == 0) {
                dp[n] = Math.min(recur(n / 3), recur(n - 1)) + 1;
            } else if (n % 2 == 0) {
                dp[n] = Math.min(recur(n / 2), recur(n - 1)) + 1;
            } else {
                dp[n] = recur(n - 1) + 1;
            }
        }
        return dp[n];
    }
}

위의 것이 Top-Down 방식, 아래의 것이 Bottom-Up 방식이다.

아무래도 호출이 많다보니 메모리도 많이 먹고 시간초도 조금 더 걸리는 모습이다.

그동안 늘 Top-Down방식에 익숙해져서 하나로만 구현해 왔는데, 이렇게 둘을 직접 비교해보니 생각보다 메모리나 시간차가 많이 나서 한번 더 생각을 하게 만드는 문제였던거 같다.

그리고 다시한번 느꼈지만.. 늘 메서드의 호출 순서, 그리고 엣지 케이스를 테스트 하는것을 소홀히 하지 않도록 다시 한번 깨닳을 수 있는 시간이였다.

저작자표시

'JAVA > 코딩 테스트' 카테고리의 다른 글

(JAVA) 백준 문제 풀이 - 동적계획법 단계 - 2565 전깃줄 (골드 5) (1)	2023.10.29
(JAVA) 백준 문제 풀이 - 동적계획법 단계 - 2156번 포도주 시식(실버 1) (0)	2023.10.28
(JAVA) 백준 문제 풀이 - 동적계획법 단계 - 1149번 RGB거리 (실버1) (0)	2023.10.26
(JAVA)백준 문제 풀이 - 동적계획법 단계 - 11053번 가장 긴 증가하는 부분 수열 (실버 2) (1)	2023.10.23
(JAVA)백준 문제 풀이 - 동적계획법 단계 - 12865번 평범한 배낭 (골드 5) (1)	2023.10.21

현재글(JAVA) 백준 문제 풀이 - 동적계획법 단계 - 1463번 1로 만들기 (실버3)

백준, HTTP, 이분탐색, HTTP메서드, 덱, HTML메서드, 정렬, 추가 기능들, 자바, 소스트리, 자료구조, Git, 동적계획법, Java, oracle, 기초부터, HTML API, 코딩테스트, 분할정복, 2차원 배열,

Today :
Yesterday :

코드저장소