[DP] 1463번 : 1로 만들기 (Java)

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

1463번: 1로 만들기

 

 

import java.io.*;

public class Main {

	 public static void main(String[] args) throws IOException {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 
		 int x = Integer.parseInt(br.readLine()); 
		 int dp[] = new int[x+1]; // 입력 받은 정수를 배열에 저장 
		 dp[0] = dp[1] = 0; // 3) 초기값 정의 (0과 1을 1로 만들 수 없음)
		 
		 for(int i=2; i<=x; i++) {
			 dp[i] = dp[i-1] +1;
			 if(i%2==0) dp[i] = Math.min(dp[i], dp[i/2]+1);
			 if(i%3==0) dp[i] = Math.min(dp[i], dp[i/3]+1);
		 }
	     System.out.println(dp[x]);
	}

}

https://www.youtube.com/watch?v=5leTtB3PQu0

https://velog.io/@kimmjieun/%EB%B0%B1%EC%A4%80-1463%EB%B2%88-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0-Java-%EC%9E%90%EB%B0%94

 

처음 작성 했던 코드

import java.util.*;

public class Main {

		public static int DP(int x) {
			if(x%3==0) return x/3;
			if(x%2==0) return x/2;
			else return x-=1;
			return DP(x-1) + DP(x);
					
		// 이미 계산된 결과를 저장하는 영역 필요	
		
		}
		
		
		public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int[] arr = new int[x];
        sc.close();

        System.out.println(DP(x));
    }

}