[BOJ] 백준 1463번 - 1로 만들기 (Java)

문제

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

1463번: 1로 만들기

 

풀이 (Top-Dowm 방식)

주어진 입력값(N)을 1로 만드는 최소 연산 횟수 구하기

할 수 있는 연산은 3가지
- 3으로 나누어 떨어질 경우 3으로 나누기
- 2로 나누어 떨어질 경우 2로 나누기
- 1 빼기

입력 값이 10일 경우, 10을 1로 만드는 과정은
A) 10 -(2로 나누기)→ 5 -(1빼기)→ 4 -(2로 나누기)→ 2 -(2로 나누기)→ 1
B) 10 -(1빼기)→ 9 -(3으로 나누기)→ 3 -(3으로 나누기)→ 1
이렇게 여러 방법이 존재하지만 A방법은 연산을 4회 수행하고, B방법은 연산을 3회 수행하기 때문에 최소 연산 횟수는 3을 출력해줘야 한다.

예를 들어 아래와 같이 코드를 작성하면 절대 B방법으로는 진행되지 않는다.

while(n > 1) {
	if(n % 3 == 0) {
		n = n / 3;
	}else if(n % 2 == 0) {
		n = n / 2;
	}else {
		n -= 1;
	}
	count++;
}

 

최소 연산 횟수를 얻어내는 고정된 규칙이 없기 때문에 N에서 가능한 모든 연산 과정을 수행하고, 이 중에서 최소 연산 횟수를 출력하는 것이 최선이다.

• 3과 2로 나누어 떨어질 경우 (=6으로 나누어 떨어질 경우)
  
  • 3으로 나누는 경우
  • 2로 나누는 경우
  • 1을 빼는 경우
• 3으로만 나누어 떨어질 경우
  • 3으로 나누는 경우
  • 1을 빼는 경우
• 2로만 나누어 떨어질 경우
  
  • 2로 나누는 경우
  • 1을 빼는 경우
• 3 또는 2로 나누어 떨어지지 않는 경우
  • 1을 빼는 경우

 

코드 (Top-Down 방식)

import java.util.Scanner;

public class Main {
	static Integer[] dp;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		dp = new Integer[n + 1];
		dp[0] = dp[1] = 0;
		
		System.out.println(recur(n));
	}
	
	static int recur(int n) {
		if(dp[n] == null) {
			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-1), recur(n / 3)) + 1;
			}else if(n % 2 == 0) {
				dp[n] = Math.min(recur(n-1), recur(n / 2)) + 1;
			}else {
				dp[n] = recur(n - 1) + 1;
			}
		}
		return dp[n];
	}
}

 

풀이 (Bottom-Up 방식)

• 1로 만들어야 할 수 N을 입력받은 뒤, 
  2~N까지 수들에 대한 최적의 해(최소 연산 횟수)를 DP 테이블에 차례로 저장한다.
• 예를 들어 N이 2일 경우, 2를 1로 만드는데 필요한 최소 연산 횟수는 아래 두 가지 경우의 연산 횟수 중 최솟값이다.
  • 첫번째 연산이 -1일 경우
  • 첫번째 연산이 /2일 경우 
• 각 경우에서 최소 연산 횟수는 아래와 같기 때문에, f(2)의 값을 구하기 위해서는 f(1)의 값이 필요하다.
  • 2-1의 값(1)을 1로 만들기 위한 최소 연산 횟수(dp[1]) + -1연산 한번 = 0 + 1 = 1
  • B. 2/2의 값(1)을 1로 만들기 위한 최소 연산 횟수(dp[1]) + /2연산 한번 = 0 + 1 = 1

• 이해가 되지 않는 다면 N을 6으로 바꿔서 생각해보자.
  이 경우에는 아래 세 가지 경우에서 연산 횟수 중 최솟값을 구해야 한다.
  • 첫번째 연산이 -1일 경우
  • 첫번째 연산이 /2일 경우
  • 첫번째 연산이 /3일 경우
• 각 경우의 최소 연산 횟수는 아래와 같으며,
  세 가지 값을 비교해본 결과 6을 1로 만들기 위한 최소 연산횟수는 2임을 알 수 있다.
  • 6-1의 값을 1로 만들기 위한 최소 연산 횟수(=dp[5]) + 1 = 3+1 = 4
  • 6/2의 값을 1로 만들기 위한 최소 연산 횟수(=dp[3]) + 1 = 1+1 = 2
  • 6/3의 값을 1로 만들기 위한 최소 연산 횟수(=dp[2]) + 1 = 1+1 = 2

• 즉, 문제의 정답인 f(N)값을 구하기 위해서는 f(2)~f(N-1) 값이 앞서 구해져야 한다. => BottomUp 방식
  'N을 1로 만드는 최소 연산 횟수' 라는 큰 문제를 2~N까지의 작은 문제들로 쪼개는 DP 문제

 

코드 (Bottom-Up 방식)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // DP 테이블 (각 숫자를 1로 만드는 데 필요한 최소 연산 횟수)
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            // 1을 빼는 경우
            dp[i] = dp[i - 1] + 1;
            // 2로 나누어 떨어지는 경우
            if(i % 2 == 0)
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            // 3으로 나누어 떨어지는 경우
            if(i % 3 == 0)
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
        }
        System.out.println(dp[n]);
    }
}

 

---

DP 문제 접근법

Dynamic Programming(DP)

동적 계획법, 하나의 문제를 작은 문제들로 쪼개서 해결하는 방식
Problem과 Sub-Problem이 무엇인지, 점화식(어떤 수열의 각각의 항들의 관계를 나타낸 식)을 파악하는 것이 관건
이미 계산된 결과(Sub Problem 결과 값)는 메모 배열에 저장하여 두번 계산하지 않도록 한다.
(= 수열을 배열이나 리스트를 이용해 표현)

• Top-Down 방식
  : 큰 문제 → 작은 문제, 재귀문을 이용해서 계산하는 방식, 호출스택 한계(maximun recursion error) 주의
• Bottom-Up 방식
  : 작은 문제 →  큰 문제, 반복문을 이용해서 계산하는 방식

 

Dynamic Programming 조건

1. 최적 부분 구조(Optimal Substructure)
   큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제(Overlapping SubProblem)
   동일한 작은 문제를 반복적으로 해결해야 한다. (점화식 → 재귀/반복문)

 

Dynamic Programming 접근 방식

• 주어진 문제가 다이나믹 프로그래밍 유형임을 파악 (분할 정복과 구분)
• 그리디, 구현, 완전 탐색 등 다른 알고리즘 방식으로 문제를 해결할 수 있는지 컴토
• 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤(Top-Down) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용

 

피보나치 수열 Bottom-Up 방식

public class DP_BottomUp {
    public static long[] d = new long[100];

    public static void main(String[] args) {
        // 첫번째, 두번째 피보나치수는 고정
        d[1] = 1;
        d[2] = 1;
        int n = 50;         // 50번째 피보나치 수 계산

        // 상향식 반복문
        for (int i = 3; i <= n; i++) {
            System.out.print("f(" + i + ") ");
            d[i] = d[i - 1] + d[i - 2];
        }

        System.out.println(d[n]);
    }
}

 

피보나치 수열 Top-Down 방식

public class DP_TopDown {

    public static long[] d = new long[100];         // 계산 결과 메모

    // 재귀 함수
    public static long fibo(int x) {
        System.out.print("f(" + x + ") ");
        // 종료 조건, 첫번째와 두번째 피보나치 수는 1로 고정
        if (x == 1 || x == 2)
            return 1;

        // 이미 계산한 적 있는 문제라면 결과 반환
        if (d[x] != 0)
            return d[x];

        // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
        d[x] = fibo(x - 1) + fibo(x - 2);
        return d[x];
    }

    public static void main(String[] args) {
        System.out.println(fibo(50));
    }
}

 

재귀함수

• 무한재귀로 인한 호출스택 한계를 방지하기 위해 종료조건을 지정해야 한다.
  ex) if(x == 1) return 1; 매개변수 x값이 1일 경우 같은 함수를 다시 호출하지 않고 1을 반환. =재귀 후 최초의 반환
• 앞서 이미 한번 해결한 적이 있는 문제를 다시 해결해서 값을 구하는 경우를 주의

 

---

[참고]

• Nocode, 코딩테스트 다이나믹 프로그래밍, https://youtu.be/eJC2oetXaNk