[백준] 1463 : 1로 만들기 JAVA 풀이

N을 입력받고

N이 3으로 나눠떨어진다면 나누기 3을,

2로 나눠떨어진다면 나누기 2를,

두 경우에 해당되지 않으면 1을 빼는 것을 반복해 1을 만드는 문제다.

 

while문을 사용해서 N이 1이 될 때까지 if문을 이용해 연산을 하고, 카운트를 셌으나 시간초과가 나왔다.

그리고 이 블로그를 참고해서 문제를 해결했다.

 

https://st-lab.tistory.com/133

 

1. N을 입력받는다.

2. 메모이제이션을 하기 위해 N+1 크기의 Integer 배열 dp를 생성한다.

    (Integer는 기본값이 null이고 int형으로 바꾸지 않으면 연산을 할 수 없는 Wrapper class이다.

    int형은 기본값이 0이기 때문에 아직 방문하지 않은 값인지 판단하려면

    배열 전체를 -1같은 값으로 초기화를 하는 과정이 추가적으로 필요하다.

    따라서 편의상 배열을 Integer형으로 선언했다.)

3. 재귀함수를 작성한다.

    N은 2와 3의 배수인 6으로 나누어 떨어지거나,

    3으로만 나누어떨어지거나,

    2로만 나누어떨어지거나,

    위 조건들을 하나도 만족하지 않을 경우로 나뉜다.

    각각의 경우에서 연산의 횟수가 최소일 때를 찾아서 반환하도록 한다.

 

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

public class Main{
	// 메모이제이션을 하기 위한 배열 생성
    static Integer[] dp;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        dp = new Integer[N+1];
        dp[0] = dp[1] = 0;
        
        System.out.print(recur(N));
    }
    static int recur(int N){
    	// 방문하지 않았던 수라면 
        if(dp[N]==null){
        	// 6으로 나눠떨어진다면
            // N-1, N/3, N/2일 때 함수를 재귀호출해서 연산횟수가 최소인 것을 찾는다
            // recur(N-1) 이런 식으로 연산을 수행한 값을 함수에 넘겨주기 때문에
            // 연산횟수에 +1을 해준다
            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/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];
    }
}

이건 코드를 짜는 과정이 잘 이해가 되지 않아서 N이 4일 때 값들이 변화하는 걸 적어본 것이다.