[코딩테스트] 다이나믹 프로그래밍(1로 만들기)

reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.

1로 만들기(백준 1463번)

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

문제

• 정수 X에 사용할 수 있는 연산 세 가지

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

어떤 정수 N에 위와 같은 연산을 선택해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 구하는 문제

풀이

• X -> X / 3 , X -> X / 2 , X -> X - 1
• 큰 문제가 작은 문제의 정답을 이용할 수 있다.
• X를 X/3 으로 만들고, X/3을 1로 만든다. 그 1로 만드는 횟수에 +1 하면 X를 X/3 하고 1로 만드는 횟수와 같아진다.
• X가 12라면 /3 = 4, /2 = 6, -1 = 11일때 4를 1로 만드는 법 2회, 6을 1로 만드는 법 2회, 11을 1로 만드는 법 4회 필요하다 했을 때 위처럼 작은 문제를 풀어 미리 구한 값을 이용해서 12를 1로 만드는 최소값을 구하면 3이 된다.
• 점화식 난이도가 낮은 경우는 문제에서 구해야 하는 값과 같은 경우가 많다.
• 점화식 : D[N] = N을 1로 만드는 최소 연산 횟수
  • 다이나믹으로 풀 수 있는 건 어떤 큰 문제가 한 단계와 나머지 전체 단계로 나누어지는 경우가 많다.
  • N을 N/3으로 만들고 N/3을 1로 만든다. N -> N/3은 1번이고 N/3 -> … -> 1 은 D[N/3]이다. 따라서 1+D[N/3] 이 된다.
  • 2로 나누는 경우엔 1+D[N/2]
  • 1빼는 경우엔 1+D[N-1]
  • D[N] = min(D[N/3], D[N/2], D[N-1])+1
  • 단 조건, D[N/3] 은 N%3==0 일 때, D[N/2]는 N%2==0일 때.
• 다이나믹에서 가장 중요한 것 중 하나는 가장 작은 크기의 문제를 찾는 것이다. 이 문제에선 1이다. 1->1 0번. 아무 연산도 사용하지 않으면 됨. D[1] = 0 (N≥2)
• 3을 나누는 것, 2로 나누는 것, 1을 빼는 우선순위로 N을 1로 만드는 건 반례 존재(10)

Top-down 방식

import java.util.*;

public class Main {
	static int memo[];
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		memo = new int[n+1];
		System.out.println(go(n));
	}

	private static int go(int n) {
		if(n==1)
			return 0;
		if(memo[n]>0) //memo[n]에 값이 0보다 크다면 이미 실행했던 결과가 있단 뜻이니 return memo[n]
			return memo[n];
		memo[n] = go(n-1)+1; // 1빼기
		if(n%3==0) { //3나누기
			int temp = go(n/3)+1;
			if(memo[n]>temp)
				memo[n]=temp;
		}
		if(n%2==0) { //2나누기
			int temp = go(n/2)+1;
			if(memo[n]>temp)
				memo[n]=temp;
		}
		return memo[n];
	}
}

Bottom-up 방식

import java.util.*;

public class Main {
	static int ans = 0;
	static int memo[];
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		memo = new int[n+1];
		memo[1]=0; //1일때 값을 먼저 정의해줘야 함
		for(int i=2; i<=n; i++) {
			memo[i] = memo[i-1]+1;
			if(i%2==0 && memo[i]>memo[i/2]+1) {
				memo[i] = memo[i/2]+1;
			}
			if(i%3==0 && memo[i]>memo[i/3]+1) {
				memo[i] = memo[i/3]+1;
			}
		}

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