백준 1463번 : 1로 만들기

✍️ 문제 풀이

---

• 접근법
  DP(Dynamic Programming)
Bottom-Up vs Top-Down
재귀

💻 java 구현 코드

---

📍 Bottom-Up

반복문을 사용하여 DP테이블(각 숫자를 1로 만드는데 필요한 최소 연산 횟수를 저장) 값을 1부터 N까지 차례대로 완성시킨다.

package ch10_DynamicProgramming;

import java.util.Scanner;

public class p1463 {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		
		int[] dp = new int[N + 1];  // DP테이블 (각 숫자를 1로 만드는데 필요한 최소 연산 횟수)
		
		dp[1] = 0;  // 초기값 세팅 
		
		for (int i = 2; i <= N; i++) {
			
			int val1 = N; int val2 = N; 
			
			if (i % 3 == 0) val1 = dp[i / 3] + 1;  // 3으로 나누어 떨어지면, 3으로 나누기
			if (i % 2 == 0) val2 = dp[i / 2] + 1;  // 2로 나누어 떨어지면, 2로 나누기
			int val3 = dp[i - 1] + 1;  // 1 빼기
			
			dp[i] = Math.min(val1, Math.min(val2, val3));
		}
		System.out.println(dp[N]);
	}
}

📍 Top-Down

재귀를 사용하여 구현

package ch10_DynamicProgramming;

import java.util.Scanner;

public class p1463 {
	
	static Integer[] dp;  // DP테이블 (각 숫자를 1로 만드는데 필요한 최소 연산 횟수)

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		
		dp = new Integer[N + 1];
		dp[0] = dp[1] = 0;  // 초기값 세팅
		
		if (N == 1)
			System.out.println(0);
		else
			System.out.println(cal(N));
	}
	
	static int cal(int N) {
		
		if (dp[N] == null) {  // 값이 구해져있지 않으면
			if (N % 6 == 0)  // 6으로 나눠지면
				dp[N] = Math.min(cal(N / 3), Math.min(cal(N / 2), cal(N - 1))) + 1;
			else if (N % 3 == 0)  // 3으로 나눠지면
				dp[N] = Math.min(cal(N / 3), cal(N - 1)) + 1;
			else if (N % 2 == 0)  // 2로 나눠지면 
				dp[N] = Math.min(cal(N / 2), cal(N - 1)) + 1;
			else  //2와 3으로 나누어지지 않으면
				dp[N] = cal(N - 1) + 1;
		}
		
		return dp[N];
	}
}

💡 문제 해결

---

💢 예상과 다른 출력값
계속 원하는 출력값이 나오지 않는 상황이 반복되었다. 코드를 아무리 봐도 문제가 없는 것 같아 보여서 결국 GPT한테 도움을 요청했더니,,, 정말 허무하게도 % 연산자 대신 / 연산자를 사용하여 발생한 문제였다.ㅎ
이런 실수 한 번 하면 다음부턴 주의해서 사용하게 되어서 시간 낭비했다고 생각하지 않으려고 한다. 👍

🧷 null값 활용

Java에서 Integer 객체 배열을 생성하면 기본적으로 각 요소는 null로 초기화된다. Integer 클래스의 객체 배열이므로 객체 자체가 null로 초기화되기 때문이다.