[백준-자바] N_12852 1로 만들기 2

0woy·2024년 1월 25일
0

코딩테스트

목록 보기
8/40
post-thumbnail

📜 문제

- 숫자 X를 입력 받고, 아래의 3가지 방법을 사용해 1로 만드는 연산의 최소 횟수 및 과정 출력.

방법

  • 숫자가 3으로 나누어 떨어지면 3으로 나눔
  • 숫자가 2로 나누어 떨어지면 2로 나눔
  • 숫자에서 1을 뺌

숫자 X를 1로 만드는 과정을 10까지 만들어 보자

숫자최소 연산 횟수과정
101
212 1
313 1
424 3 1 / 4 2 1
535 4 3 1 / 5 4 2 1
626 3 1 / 6 2 1
737 6 3 1 / 7 6 2 1
838 4 2 1
929 3 1
10310 9 3 1

X는 3으로 나누어지는 수, 2로 나누어 떨어지는 수, 2와 3 모두 나누어 떨어지는 수, 2와 3 모두 나누어 떨어지지 않는 수 로 총 4가지 경우가 있다.

1) 2로 나누어 떨어지는 경우

EX) X = 8
8의 연산과정은 8 4 2 1 로 총 3번의 연산이 수행된다.
그런데, 4 2 1 연산은 X가 4인 경우의 연산과정과 동일하다.
즉, 최소 연산 횟수는 dp[8] = dp[8/2]+1 로 식을 세울 수 있다.

EX) X = 4
그런데, 4의 경우 연산 과정이 4 3 1 또는 4 2 1로 두 개가 나온다.
4 2 1 연산의 경우 8의 예시와 동일한 방식이지만, 4 3 1의 경우는 4가 3보다 +1이 크기때문에 3의 연산에서 1을 더한 값과 같다.
즉, dp[4] = dp[4-1]+1 로도 식을 세울 수 있다.

2) 3으로 나누어 떨어지는 경우

EX) X = 9
9의 연산과정은 9 3 1 로 총 2번의 연산이 수행된다.
2로 나누어 떨어지는 식과 같이 dp[9] = dp[9/3]+1로 최소 연산 횟수 식을 세울 수 있다.

1) 과 마찬가지로 8의 연산과정에서 +1한 값이 9가 되므로, dp[9] = dp[9-1]+1의 식도 세울 수 있다.

3) 2와 3 모두 나누어 떨어지는 경우

X가 2와 3 모두 나누어 떨어지는 경우는 1) 과 2) 두 가지 방법을 모두 사용할 수 있다.
dp[X/2]+1 또는 dp[X/3]+1 값 중 더 작은 값을 취하면 된다.

4) 2와 3 모두 나누어 떨어지지 않는 경우

모두 나누어 떨어지지 않는 경우는 1을 빼는 연산만 사용할 수 있으므로,
dp[x] = dp[x-1]+1 의 식이 성립된다.

이미 dp[x-1]의 최소 연산 횟수는 구해져 있음.


✍ 부분 코드 설명

점화식을 통해 최소 연산 횟수 구하기

		dp[1] =0;
        dp[2] =1;
        dp[3] =1;
        
     for(int i=4;i<=n;i++){
            int tmp = Integer.MAX_VALUE;
            if(i%2==0) tmp = Math.min(dp[i/2], tmp);
            if(i%3==0) tmp = Math.min(dp[i/3], tmp);
            tmp = Math.min(dp[i-1],tmp);
            dp[i] = tmp+1;
        }
        sb.append(dp[n]+"\n");

dp 배열은 각 인덱스가 되는 숫자의 최소 연산 횟수를 저장하는 배열이다.
1, 2, 3의 경우 미리 초기화 한다.

a. tmp 변수를 선언하고 초기화 한다.
b. 2로 나누어 떨어지는 경우 dp[i/2]와 tmp 값 중 더 작은 값을 tmp에 저장한다.
c. 3으로 나누어 떨어지는 경우 dp[i/3]과 tmp 값 중 더 작은 값을 tmp에 저장한다.
d. 이전 값(dp[i-1]) tmp 값 중 더 작은 값을 tmp에 저장한다.

위 과정은 조건에 따라 tmp 값을 갱신 하면서 결과적으로 최소 연산 횟수를 구한다.


연산 과정 구하기

	 while (true){
            sb.append(n+" ");
            int tmp = Integer.MAX_VALUE;
            int idx=-1;
            if(n==1) break;

            if(n%2==0){
                if(dp[n/2]<tmp){
                    tmp = dp[n/2];
                    idx = n/2;
                }
            }
            if(n%3==0){
                if(dp[n/3]<tmp){
                    tmp = dp[n/3];
                    idx =n/3;
                }
            }
            if(dp[n-1]<tmp) idx =n-1;
            n = idx;
            }

연산 과정을 구하기 위한 코드이다.

  • n이 1인 경우 연산이 종료되므로 반복문을 빠져 나간다.
  • 최소 연산 횟수를 구하는 조건식과 동일하지만, idx 값이 연산 과정이 된다.
  • 반복문 처음에 n 값을 sb에 저장한다.

🍳 전체 소스 코드

package Algorithm.DP;

import org.w3c.dom.ls.LSOutput;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class N_12852 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int [] dp = new int [n+3];

        dp[1] =0;
        dp[2] =1;
        dp[3]=1;

        for(int i=4;i<=n;i++){
            int tmp = Integer.MAX_VALUE;
            if(i%2==0) tmp = Math.min(dp[i/2], tmp);
            if(i%3==0) tmp = Math.min(dp[i/3], tmp);
            tmp = Math.min(dp[i-1],tmp);
            dp[i] = tmp+1;
        }
            sb.append(dp[n]+"\n");
        while (true){
            sb.append(n+" ");
            int tmp = Integer.MAX_VALUE;
            int idx=-1;
            if(n==1) break;

            if(n%2==0){
                if(dp[n/2]<tmp){
                    tmp = dp[n/2];
                    idx = n/2;
                }
            }
            if(n%3==0){
                if(dp[n/3]<tmp){
                    tmp = dp[n/3];
                    idx =n/3;
                }
            }
            if(dp[n-1]<tmp) idx =n-1;
            n = idx;
            }
        System.out.println(sb);
        }
    }


✨ 결과

가장 최근 결과가 설명한 코드로 문제를 푼 결과이다.
두 번째 결과를 보면 메모리와 시간을 상당히 잡아 먹었는데, 이에 충격 먹고 다른 분의 코드를 참고 후 이해하여 정리해서 올렸다.

연산 횟수를 구하는 점화식을 도출하는 건 어렵지 않았는데 바보같이 연산 과정을 구하는 일을 많이 돌아갔다...
그래도 뿌듯한 점은 실버 1 문제를 풀었다는 것이다..
엊그제만 해도 실버 3도 많이 슬펐는데 뇌가 말랑말랑 해졌나 보다 히히.


🍰 비효율 코드

조건식 하나하나 작성하기

시간과 메모리를 많이 잡아 먹은 코드는 조건식을 하나하나 작성했다. 다시 봐도 왜 이렇게 풀었는지 모르겠다. 많이 힘들었나,,,,

        switch (n){
            case 1:
                dp[1] =0;
                sol[1]= "1";
                break;
            case 2:
                dp[2]=1;
                sol[2]="1 2";
                break;
            case 3:
                dp[3]=1;
                sol[3] ="1 3";
                break;
        }

        if(n>3) {
            dp[1] =0;
            sol[1]= "1";
            dp[2] =1;
            sol[2]="1 2";
            dp[3] =1;
            sol[3] ="1 3";
            for (int i = 4; i <= n; i++) {
                if(i%3==0&&i%2!=0) {
                    if(dp[i/3]<dp[i-1]){
                        dp[i] = dp[i/3]+1;
                        sol[i] = sol[i/3]+" "+i;
                    }
                    else{
                        dp[i]=dp[i-1]+1;
                        sol[i]=sol[i-1]+" "+i;
                    }
                }
                else if(i%3==0&&i%2==0){
                    if(dp[i/3]<dp[i/2]){
                        dp[i] = dp[i/3]+1;
                        sol[i] = sol[i/3]+" "+i;
                    }
                    else{
                        dp[i]=dp[i/2]+1;
                        sol[i]=sol[i/2]+" "+i;
                    }
                }

                else if(i%2==0){
                    if(dp[i/2]<dp[i-1]){
                        dp[i] = dp[i/2]+1;
                        sol[i] = sol[i/2]+" "+i;
                    }
                    else{
                        dp[i]=dp[i-1]+1;
                        sol[i]=sol[i-1]+" "+i;
                    }
                }
                else{
                    dp[i]=dp[i-1]+1;
                    sol[i] = sol[i-1]+" "+i;
                }
            }
        }
      

세상에서 가장 비효율적인 조건식이다.
내 문제가 여기서 드러나는데, else if가 없으면 세상이 무너진다고 생각한다.
그리고 반복문 하나로 모든 걸 끝내려고 한다.

본문에서 설명한 코드처럼 if만 사용해도 모든 조건식을 깔끔하게 확인할 수 있는데, 막상 조건을 따져야 하는 문제만 보면 하나하나 조건을 만들어준다.

연산과정 구한다고 String 배열 선언한 것도 상당히 괴랄하다.
급할 수록 돌아가라고 하지만 적당히 돌아가야지 나처럼 너무 돌아가면 안 된다

0개의 댓글