[이코테] Chapter 8. 다이나믹 프로그래밍 (java)

📍개념

1. 다이나믹 프로그래밍

큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

따라서 점화식부터 세운다

---

2. 탑다운 방식

• 재귀 함수를 이용하는 방법
• 메모제이션: 한 번 구한 결과를 메모리 공간에 메모해 두고, 같은 값을 다시 호출하면 메모리에서 꺼내오는 기법. 탑다운 방식에서 사용 가능

public static long fibo(int n) {
		// 종료 조건
		if (n == 1 || n == 2)
			return 1;

		// 계산한 적 있다면 그 값 반환
		if (d[n] != 0)
			return d[n];

		// 계산한 적 없다면 계산 후 값 반환
		d[n] = fibo(n - 1) + fibo(n - 2);
		return d[n];
	}

---

3. 보텀업 방식

• 반복문을 이용하는 방법
• 보텀업 방식으로 구현하는 것을 권장. 스택 크기가 한정되어 있을 수 있기 때문. 

public class Main {
	public static void main(String[] args) {
		long[] d = new long[100];
		int n = 50;
		d[1] = 1;
		d[2] = 1;
		for (int i = 3; i <= n; i++) {
			d[i] = d[i - 1] + d[i - 2];
		}
		System.out.println(d[n]);
	}
}

---

📖 [예제 8-1] 1로 만들기

문제설명

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다.

ⓐ X가 5로 나누어 떨어지면 5로 나눈다.
ⓑ X가 3으로 나누어 떨어지면 3으로 나눈다.
ⓒ X가 2로 나누어 떨어지면 2로 나눈다.
ⓓ X에서 1을 뺀다.

정수가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오

입력조건

첫째 줄에 정수 X가 주어진다.(1 <= X <= 30,000)

출력조건

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 🔑 풀이

i-1, i/2, i/3, i/5 중 가장 작은 값을 선택한다.

• 1은 그자체로 결과이므로 d[1]=0
• d[n]=min(d[n-1], d[n/2],  d[n/3], d[n/5]) + 1

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int x = scan.nextInt();

		int[] d = new int[x + 1];
		for (int i = 2; i <= x; i++) {
			d[i] = d[i - 1] + 1;
			if (i % 2 == 0)
				d[i] = Math.min(d[i], d[i / 2] + 1);
			if (i % 3 == 0)
				d[i] = Math.min(d[i], d[i / 3] + 1);
			if (i % 5 == 0)
				d[i] = Math.min(d[i], d[i / 5] + 1);
		}

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

---

📖 [예제 8-2] 개미 전사

문제

개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자.

{1, 3, 1, 5}

이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다. 개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다. 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 식량창고의 개수 N이 주어진다. (3<=N<=100)
• 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0<=K<=1,000)

출력 조건

• 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

🔑 풀이

i를 선택하는 경우와 선택하지 않는 경우 중 더 큰 값을 선택한다

• d[0]은 비교할 게 없으므로 선택. K[0]
• d[1]은 첫 번째 값과, 두 번째 값 중 더 큰 값 선택. max(K[0], K[1])
• d[n]=max(d[n-1], d[n-2] + K[n])

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] K = new int[N];
		for (int i = 0; i < N; i++) {
			K[i] = scan.nextInt();
		}

		int[] d = new int[N];
		d[0] = K[0];
		d[1] = Math.max(K[0], K[1]);
		for (int i = 3; i < N; i++) {
			d[i] = Math.max(d[i - 1], d[i - 2] + K[i]);
		}
		System.out.println(d[N - 1]);
	}
}

---

📖 [예제 8-3] 바닥 공사

문제

• 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다.
• 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다.
• 이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.
• 예를 들어, 2X3 크기의 바닥을 채우는 경우의 수는 5가지이다.

입력 조건

• 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000)

출력 조건

• 첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

 

🔑 풀이

왼쪽부터 i-1번째까지 채워진 경우와 i-2번째까지 채워진 경우를 나눠 구한다.

1. i-1번째까지 덮개가 채워진 경우: 2x1로 채우는 한가지 경우밖에 없으므로 d[i] = d[i-1]
2. i-2번째까지 덮개가 채워진 경우: 1x2 두 개로 채우는 경우, 2x2로 채우는 경우가 있으므로 d[i] = d[i-2] * 2

따라서 두 경우의 값을 더하면 d[i]가 된다.

• (1x2): d[1]=1 
• (2x2): d[2]=3 
• (nx2): d[n]=d[n-1]+d[n-2]*2 

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] d = new int[N + 1];
		d[1] = 1;
		d[2] = 3;
		for (int i = 3; i <= N; i++) {
			d[i] = (d[i - 1] + d[i - 2] * 2) % 796796;
		}
		System.out.println(d[N]);
	}
}

---

📖 [예제 8-4] 효율적인 화폐 구성

문제

• N가지 종류의 화폐가 있다.
• 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.
• 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
• 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

입력 조건

• 첫째 줄에 N,M이 주어진다(1<= N <= 100, 1<= M <= 10,000)
• 이후의 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.

출력 조건

• 첫째 줄에 경우의 수 X를 출력한다.
• 불가능할 때는 -1을 출력한다.

 

🔑 풀이

✅ int[] arr: 화폐종류

• d[화폐종류] = 1 
• d[n] = d[n-화폐종류] + 1 중 최솟값

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int M = scan.nextInt();
		int[] arr = new int[N];
		int[] d = new int[10001];
		for (int i = 0; i < N; i++) {
			arr[i] = scan.nextInt();
			d[arr[i]] = 1;
		}

		for (int i = arr[0] + 1; i <= M; i++) {
			if (d[i] == 0) {
				if (d[i - arr[0]] != 0)
					d[i] = d[arr[0]] + d[i - arr[0]];
				for (int j = 1; j < N; j++) {
					if (i - arr[j] > 0) {
						if (d[i - arr[j]] != 0) {
							d[i] = Math.min(1 + d[i - arr[j]], d[i]);
						}
					}
				}
			}
		}

		if (d[M] == 0)
			System.out.println("-1");
		else
			System.out.println(d[M]);
	}
}

---

점화식 못구하겠어서 3번까지 베낌

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

고등학교때도 수열문제는 걍 넘어간 사람이 어른이 되면 이렇게된다...

4번은 문제 잘못 읽고 한참 고민하다가? 풀어냈습니다

많이 연습해야지~~^^