Dynamic Programming 체득을 위해 예제 문제 몇가지를 풀어보려고 한다.
1. 1로 만들기(난이도 ⭐☆)
2. 개미 전사(난이도 ⭐⭐)
3. 바닥 공사(난이도 ⭐☆)
1. 1로 만들기
해당 문제는 피보나치 수열을 dynamic programming으로 풀이할때와 거의 동일한 문제라고 볼 수 있다.
이또한 피보나치 수열의 문제를 풀 때 사용했던 가지치기 도식을 떠올려주면 풀 수 있다.
우선 어떤 문제인지 살펴보자.
https://baekwisdom02.tistory.com/124
알고리즘 개념정리: Dynamic Programming
Dynamic Programming이란?알고리즘 문제를 풀이할 때 최적의 해를 구하기에 연산량이 많아서 시간이 많이 필요하거나, 메모리 공간이 많이 필요한 문제들이 있다. 그래서 문제를 풀 때 연산 속도와 메
baekwisdom02.tistory.com
정수 X가 주어질 때, 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
a. X가 5로 나누어 떨어지면, 5로 나눈다.
b. X가 3으로 나누어 떨어지면, 3으로 나눈다.
c. X가 2로 나누어 떨어지면, 2로 나눈다.
d. X에서 1을 뺀다.
정수 X가 주어졌을 때 위 연산 4개를 사용해 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하여라.
단, 시간 제한은 1초 & 메모리 제한 128MB
ex) 입력: 26, 출력: 3
🌿 풀이과정
이것도 피보나치 수열 문제를 풀 때처럼, 풀이 과정을 도식화할 수 있다.
위와 같이 풀이과정을 도식화했을 시, f(1)에 가장 먼저 도달하는 연산 횟수가 몇회인지를 구하면 되는 문제이다.
26일 때는 26-1 = 25, 25/5 = 5, 5/5 = 1로 총 3회의 연산을 수행했을 때가 가장 최단 경로이다.
이러한 알고리즘을 아래와 같이 코드로 구현할 수 있다.
코드 풀이 보충설명을 하자면 아래와 같다.
arr[i]는 현재 수가 i일때의 연산 횟수를 저장하는 배열이다.
arr[i] = arr[i-1]+1;의 경우 i에서 -1 연산 1번을 수행해 i-1을 만들 수 있으므로
arr[i]의 연산 횟수에 빼기 연산 1회의 개수만큼을 더해주는 방식이다.
나머지 나누기 연산은, 해당 수로 나눴을 때의 나머지가 0인 경우만 이용할 수 있으므로 조건문으로 처리해준다.
arr[i]의 최소 연산 횟수는 현재 연산 횟수인 arr[i]와, arr[i/5]+1 ( = arr[i]를 5로 나눈 연산을 적용했을 때의 연산 횟수) 중 더 작은 최솟값을 선택하여 '최소 연산 횟수'를 구해나간다.
이를 i = 2 일때부터 i = X일 때까지 순회하며 연산을 수행하면 a[1] ~ a[X]까지의 최소 연산 횟수가 배열에 저장된다.
💻소스코드
#include <iostream>
using namespace std;
int main(void) {
int arr[30001] = { 0, };
int X;
cin >> X;
for (int i = 2; i < X+1; i++) {
arr[i] = arr[i - 1] + 1;
if (i % 5 == 0) {
arr[i] = min(arr[i], arr[i/5]+1);
}
if (i % 3 == 0) {
arr[i] = min(arr[i], arr[i/3] + 1);
}
if (i % 2 == 0) {
arr[i] = min(arr[i], arr[i/2] + 1);
}
}
cout << arr[X] << endl;
return 0;
}
테스트시, 손으로 구했던 26의 최소 연산 횟수 3이 일치하는 것을 확인할 수 있다.
후에 이어서 2. 개미전사와 3. 바닥공사 문제도 풀어보도록 하겠다!
2. 개미전사
이어서 Dynamic Programming 관련 문제인 '개미전사'를 풀어보도록 하겠다.
문제 조건을 먼저 살펴보자.
개미 전사가 부족한 식량을 충당하고자 메뚜기 마을의 식량 창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러개의 식량창고가 있는데 식량고는 일직선으로 이어져있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량 창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있ㄷ가. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.
입력 조건) 첫째 줄에 식량창고의 개수 N이 주어진다.(3<=N<=100)
둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다.(0<=K<=1000)
출력 조건) 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 구하시오.
입력 예시)
4
1 3 1 5
출력 예시)
8
위 문제 또한 그림을 그리면서 점화식을 어떻게 세우면 좋을지를 고민해보자.
🌿 풀이과정
경우 1) ( i - 2 )번째 식량 창고를 털기로 결정한 경우, 현재의 식량창고를 털 수 있음.
경우 2) ( i - 1 )번째 식량 창고를 털기로 결정한 경우, 현재의 식량창고를 털 수 없음.
경우 1과 경우 2 중 더 많은 식량을 벌 수 있는 경우를 택하면서, 결과적으로 N번째 식량 창고까지 도달했을 때 누적의 합이 가장 큰 경우를 선택하면 된다.
i번째 위치에 있을 때 ( i - 3)번째 식량창고부터는 어떤 경우의 수라도 선택이 가능하기 때문에 고려하지 않아도 된다.
따라서 도출되는 점화식은,
ai = max(a(i-1), a(i-2)+ki)
이때, ai는 i번째 식량창고까지 거쳐오면서 누적된 식량의 합이고, ki는 i번째 단일 식량창고 안에 있는 식량의 양이다.
더 직관적인 이해를 위해 코드를 작성하기 전에 한번 위 점화식에 따라 문제의 결과를 구해보려고 한다.
아래와 같은 식량 창고가 있을 때, 위 점화식대로 전체 식량창고에서 수확할 수 있는 가장 많은 식량의 양을 구할 수 있다.
점화식을 구하고나면 소스코드로는 아주 간단하게 구현할 수 있다.
💻소스코드
#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
int n;
cin >> n;
int *arr= new int[n];
int* result = new int[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
result[0] = arr[0];
result[1] = arr[1];
for (int i = 2; i < n; i++) {
result[i] = max(arr[i] + result[i - 2], result[i - 1]);
}
cout << result[n-1] << endl;
return 0;
}
3. 바닥공사
세번째로, Dynamic Programming의 대표 유형인 타일 맞추기 문제를 풀어보자.
문제 내용은 아래와 같다.
가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1*2의 덮개, 2*1의 덮개, 2*2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.
예를 들어 2*3 크기의 바닥을 채우는 경우의 수는 5가지이다.
입력 조건) 첫째 줄에 N이 주어진다. (1<=N<=1000)
출력 조건) 첫째 줄에 2*N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.
🌿 풀이과정
이 문제도 위의 문제들처럼, 규칙을 찾아 점화식만 잘 세우면 해결되는 문제이다.
경우의 수를 796796으로 나눈 나머지를 구하는 이유는 결과값이 너무 커지는 것을 방지하기 위해서이다.
우선 점화식을 찾기 위해서 몇단계만 그림을 그려서 파악해보고 i, (i-1), (i-2)번째에 따라 식을 구성할 수 있을지 한번 살펴보자. 세로의 길이가 무조건 2이기 때문에 i번째의 경우의 수를 구할 때 (i-1), (i-2)번째로 나누어지는 경우들에 대해서만 따져주면 될 것 같다.
문제에서 N*2 크기의 바닥에 타일을 깔기 위해 사용할 수 있는 타일의 종류는 아래 세가지와 같다.
-> (1*2), (2*1), (2*2)
N = 1 ~ N = 4일때까지 직접 그려서 가능한 타일 구성의 개수를 그려보았다.
위와 같이
N = 1일 때 경우의 수 1,
N = 2일 때 경우의 수 3,
N = 3일 때 경우의 수 5,
N = 4일 때 경우의 수가 11이었다.
N = 1일때와 N = 2일때 까지는 직관적으로 경우의 수가 1, 3인 것을 알 수 있고
N = 3일때부터 일련의 반복되는 규칙을 찾을 수 있었다.
N = 3이 된 경우, 나는 N = 2일때의 경우의 수에서 나온 타일 구성에 (1*2)짜리 타일 하나씩을 붙여주었다.
N = 2인 타일 구성에서 N = 3을 만들기 위해서는 붙일 수 있는 타일이 오직 (1*2)짜리 타일 뿐이기 때문이다.
그 다음, N = 1일 때의 경우의 수에서 나온 타일 구성에 (2*1)짜리 타일 2개 혹은 (2*2)짜리 타일 하나를 붙여
N = 3인 경우의 타일 구성을 만들 수 있었다.
(1*2)인 타일을 2개 이어 붙이는 경우는 N = 2인 타일 구성에서 (1*2)짜리 타일을 사용하는 경우와 동일한 타일 구성이 겹치기 때문에 제외했다.
N = 4인 경우도, N = 2일 때의 경우의 수에서 나온 타일 구성에 (2*1)짜리 타일 2개 혹은 (2*2)짜리 타일 하나를 붙이는 방식, 그리고 N = 3일때의 경우의 수에서 나온 타일 구성에 (1*2)짜리 타일 하나씩을 붙여주는 방식으로 타일을 확장하였다.
위 색칠된 부분을 잘 보면, 파란색으로 색칠된 부분은 기존 타일 구성에서 가로 길이를 1만큼 확장한 경우이고
분홍색으로 색칠된 부분은 기존 타일 구성에서 가로 길이를 2만큼 확장한 경우이다.
즉, 구성해야 하는 타일의 가로 길이 N = i라고 하였을 때
N = (i-1)인 타일 구성에 (1*2) 블럭 하나를 추가해 주는 경우는 N = (i-1)일때의 경우의 수와 같고
N = (i-2)인 타일 구성에 (2*1) 블럭을 두개 추가하거나 or (2*2) 블럭을 하나 추가해 주는 경우는 N = (i-2)일때의 경우의 수에 곱하기 2를 한 만큼으로 카운트 할 수 있다.
이대로 점화식을 작성해보면,
a1 = 1, a2 = 3,
ai = a(i-1) + a(i-2) * 2
위와 같은 식이 도출된다. 이때, ai는 가로 길이가 i이고 세로길이가 2인 타일을 만들수 있는 경우의 수이다.
이를 코드로 아래와 같이 간단히 구현할 수 있다.
💻소스코드
#include <iostream>
using namespace std;
int main(void) {
int N;
cin >> N;
int* arr = new int{ N+1 };
arr[1] = 1;
arr[2] = 3;
for (int i = 3; i < N + 1; i++) {
arr[i] = arr[i - 1] + arr[i - 2] * 2;
}
int result = arr[N] % 796796;
cout << result << endl;
return 0;
}