[백준-1463번 자바/java] 1로 만들기 _디버깅의 눈물

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

1463번: 1로 만들기

 

 

 

 

1로 만들기 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.15 초 (하단 참고)

128 MB

217958

71407

45749

32.214%

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

1

예제 입력 2 복사

10

예제 출력 2 복사

3

 

 

 

---

 

체크 포인트

1. 다이나믹 프로그래밍(Dynamic Programming, 동적계획법) 이용

-큰 문제를 여러 가지 작은 문제로 나누어 해결해보는 DP를 이용했다.

-그 중에서 큰 문제로부터 작은 문제로 뻗어나가는 top-down(탑다운)방식을 이용해 재귀함수로 해결했다.

 

 

2. 연산을 사용하는 횟수의 최소값 != 큰 수로 나눈 값

-이 문제를 풀 때, 무조건 큰 수로 나누는 것이 최소의 연산 사용 횟수를 보장하지 않는다!

 

예를 들어 N=10인 경우,

큰수로 나누면 10->5->4->2->1 로 총 4번의 연산이 진행되지만,

10->9->3->1 로 -1처리를 먼저 진행하면, 총 3번의 연산이 된다.

 

-따라서 최소의 연산 사용 횟수를 구하기 위해 총 4가지로 경우의 수를 구분해 접근해야 한다.

 

        	// 6으로 나눠 떨어지는 경우,
        	if(N%6==0){
        		System.out.println("  6으로 나눠 떨어지는 경우");
        		dp[N] = Math.min(solution(N-1), Math.min(solution(N/3), solution(N/2))) + 1;
        		
        	}
        	// 3으로 나눠 떨어지는 경우,
        	else if(N%3==0){
        		System.out.println("  3으로 나눠 떨어지는 경우");
        		dp[N] = Math.min(solution(N/3), solution(N-1)) + 1;
        		
        	}
        	// 2로 나눠 떨어지는 경우,
        	else if(N%2==0){
        		System.out.println("  2로 나눠 떨어지는 경우");
        		dp[N] = Math.min(solution(N/2), solution(N-1)) + 1;
        		
        	}
        	// 3하고 2 둘다 안 나눠지는 경우,
        	else{
        		System.out.println("  3하고 2 둘다 안 나눠지는 경우");
        		dp[N] = solution(N-1) + 1;
        	}

 

1)N이 6으로 나눠질 때,

->(1)N이 3으로 나눠지는 경우, (2)N이 2로 나눠지는 경우, (3)N-1을 한 경우, 총 세 가지를 비교해 최소값을 dp[N]에 입력

 

2)N이 3으로 나눠질 때,

->(1)N이 3으로 나눠지는 경우, (2)N-1을 한 경우, 총 두 가지를 비교해 최소값을 dp[N]에 입력

 

3)N이 2로 나눠질 때,

->(1)N이 2로 나눠지는 경우, (2)N-1을 한 경우, 총 두 가지를 비교해 최소값을 dp[N]에 입력

 

4)N이 3과 2로 나눠지지 않을 때,

->(1)N-1을 한 경우를 최소값으로 dp[N]에 입력

 

 

예제2를 기준으로 N=10인 경우를 예로 들 때,

 

 

위의 순서로 재귀함수가 작동하는 것을 볼 수 있다. 

 

 

3. 특이한 점

 

    static int solution(int N) {
    	// 방문했던 적이 없는 경우,
    	if(dp[N]==null){

        	
        	// 6으로 나눠 떨어지는 경우,
        	if(N%6==0){
        		dp[N] = Math.min(solution(N-1), Math.min(solution(N/3), solution(N/2))) + 1;
        		
        	}
        	// 3으로 나눠 떨어지는 경우,
        	else if(N%3==0){
                // 주석 부분을 적용할 경우 정상 정답처리
                // dp[N] = Math.min(solution(N/3), solution(N-1)) + 1;			
        		dp[N] = Math.min(solution(N-1), solution(N/3)) + 1;
        		
        	}
        	// 2로 나눠 떨어지는 경우,
        	else if(N%2==0){
                // 주석 부분을 적용할 경우 정상 정답처리
                // dp[N] = Math.min(solution(N/2), solution(N-1)) + 1;
        		dp[N] = Math.min(solution(N-1), solution(N/2)) + 1;
        		
        	}
        	// 3하고 2 둘다 안 나눠지는 경우,
        	else{
        		dp[N] = solution(N-1) + 1;
        	}
    	}
    	
    	return dp[N];
    } // end of solution

 

-Math.min()을 통해서 최소값을 비교해 구하는 과정 중에서, 순서를 바꾸었더니 시간초과로 바뀌는 문제를 발견했다.

예를 들어, solution(N/3)과 solution(N-1)의 위치만 바꾸었는데 시간초과로 변한 것이다.

하지만 정확히 어떤 문제인지 파악하지 못했기 때문에 기록을 해두고 추후 파악하려고 한다.

 

풀이

 

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

public  class Main {
	
	// 메모이제이션을 활용할 dp 배열
	static Integer[] dp;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	// 정수 N 
    	int N = Integer.parseInt(st.nextToken());
    	
    	// dp 배열 초기화(Integer 배열은 기본값이 NULL이다.)
    	dp = new Integer[N+1];
    	// 재귀 탐색을 위한 기본값 설정
    	dp[0] = dp[1] = 0;
    	
    	// 탐색 시작
    	System.out.println(solution(N));
    	
    } // end of Main
    
    
    
    // top-down(탑다운) 방식 구현
    static int solution(int N) {
    	// 방문했던 적이 없는 경우,
    	if(dp[N]==null){

        	
        	// 6으로 나눠 떨어지는 경우,
        	if(N%6==0){
        		dp[N] = Math.min(solution(N-1), Math.min(solution(N/3), solution(N/2))) + 1;
        		
        	}
        	// 3으로 나눠 떨어지는 경우,
        	else if(N%3==0){
        		dp[N] = Math.min(solution(N/3), solution(N-1)) + 1;
        		
        	}
        	// 2로 나눠 떨어지는 경우,
        	else if(N%2==0){
        		dp[N] = Math.min(solution(N/2), solution(N-1)) + 1;
        		
        	}
        	// 3하고 2 둘다 안 나눠지는 경우,
        	else{
        		dp[N] = solution(N-1) + 1;
        	}
    	}
    	
    	return dp[N];
    } // end of solution
    
} // end of Main