백준 Bottom-UP DP 문제들
알고리즘 기초 문제 중 DP 기본 문제(400)
이 중 bottom-up 방식의 기본 문제들
1. 2xN 타일링
2xn 크기의 직사각형을 1x2, 2x1 타일로 채운다
Dp 유형 중 bottom-up 방식
DP 문제를 풀때, 점화식을 찾는 방법은
1부터 차례대로 늘어놓으면서 규칙을 찾는 것이다
1
2
3
4
5
6
7
8
9
n = 1일때, 2x1 을 채우는 방법은 한가지
n = 2일때, 2x2 을 채우는 방법은 2가지
n = 3, 2x3 => 3
n = 4 : n-1 에 1x2 한조각 붙이기 + n-2에 2x1 두개 붙이기
...
dp[n] = dp[n-1] + dp[n-2] 로 점화식을 얻을 수 있다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int arr[1001];
int main() {
int n;
cin >> n;
arr[1] = 1;
arr[2] = 2;
for (int i = 3; i <= 1000; i++) {
arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
}
cout << arr[n];
return 0;
}
2. 2xN 타일링 2
1번 2xn 타일링 문제에 새로운 타일이 추가된 문제
마찬가지로 bottom-up 방식
1
2
3
4
5
6
7
8
9
10
11
n = 1 일때 => 1가지 (2x1)
n = 2 일때 => 3가지 (1x2 2개, 2x1 2개, 2x2 1개)
n = 3 일때 => 5가지
(1x2 3개 1가지 방법, 1x2 1개 + 2x1 2개를 조합한 2가지 방법, 1x2 1개 + 2x2 1개를 조합한 2가지 방법)
...
n일때 -> (n-1에 1x2를 덧붙이기) + (n-2에 2x1을 2개 덧붙이기) + (n-2에 2x2를 1개 덧붙이기)
dp[n] = dp[i-1] + dp[i-2] + dp[i-2]로 점화식을 얻을 수 있다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
int arr[1001];
int main() {
int n;
cin >> n;
arr[1] = 1;
arr[2] = 3;
for (int i = 3; i <= 1000; i++) {
arr[i] = (arr[i - 1] + arr[i - 2] + arr[i - 2]) % 10007;
}
// [n-1]에 1x2을 붙인것, [n-2]에 2x1 2개 붙인것, [n-2]에 2x2 1개 붙인것
cout << arr[n];
return 0;
}
3. 1, 2, 3 더하기
얘도 bottom up 방식
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1을 만드는 방법 : 1가지
2를 만드는 방법 : 1+1, 2
3 : 1+1+1, 1+2, 2+1, 3
4 : (3을 만든 방법에 1을 더하기) + (2를 만든 방법에 2를 더하기) + (1을 만든 방법에 3을 더하기)
...
N : (N-3을 만든 방법 개수에 1을 더하기) +
(N-2을 만든 방법 개수에 2를 더하기) +
(N-1을 만든 방법 개수에 3을 더하기)
dp[n] = dp[n-3] + dp[n-2] + dp[n-1] 로 점화식을 얻을 수 있다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
int dp[11];
int main() {
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int i = 4; i <= 10; i++) {
dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
}
int T; cin >> T;
while (T--) {
int n;
cin >> n;
cout << dp[n] << '\n';
}
return 0;
}
4. 카드 구매하기
간단 설명
모을 카드 개수 N과
카드 N개가 포함된 카드팩과 그 가격이 주어진다
P1은 카드 한개가 들어있는 카드팩. P2는 2개 이런식
이를 조합해서 구매 가격의 최대값을 구하는 문제
문제 분석
일단 점화식을 세우기 위해 규칙을 찾아본다
1
2
3
4
5
6
7
8
9
10
11
12
N = 1인 경우, 카드 한개만 구매하면됨 => p1이 최대값
N = 2인 경우, 카드 2개 구매필요 => (p1 + p1) 과 (p2)중 최대값 선택
N = 3인 경우, 카드 3개 => (p1+p1+p1) vs (p1+p2) vs (p3)
N = 4인 경우, 카드 4개 => p1 4개 vs p1 + p3 vs p2 2개 + p4
...
N => n-3개 고르고 p1 더하기, n-2개 고르고 p2 더하기, n-3개 고르고 p3 더하기 ... , n-n개 고르고 pn 고르기(하나도 안고르고 pn 선택) 중 최대값 선택
위 1,2,3 문제와 유사하나, 비교해야하는 개수가 1~N까지임
이를 점화식으로 구현하면
dp[n] = dp[n] vs dp[n-i] + p[i]. i는 1부터 N까지
필요 변수
카드 개수 int N (1<= N <= 1000)
카드 팩의 가격 int p[1001] (1 <= p <= 10000)
int dp[1001]
- dp의 최대값은 10억을 넘지 못하므로 int형으로 처리 가능 (1000 * 10000)
알고리즘
1
2
3
4
5
6
7
1. N 입력받기
2. pi 입력받기
3. dp[1], dp[2], dp[3] 구하기
4. 구한 식을 토대로 dp[n] 을 구한다
4-1. i=4부터 N까지 반복
4-2. j=1부터 i까지 반복하면서 dp[i]의 최대값을 계산한다
5. dp[n] 출력
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cmath>
#include <algorithm> // min, max 3개 인자 비교에 사용
#define MAX 1001
using namespace std;
int N;
int p[MAX];
int dp[MAX];
int main() {
freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> p[i];
}
dp[1] = p[1];
dp[2] = max(2 * p[1], p[2]);
dp[3] = max({ 3 * p[1], p[1] + p[2], p[3] });
for (int i = 4; i <= N; i++) {
for (int j = 1; j <= i; j++) {
dp[i] = max(dp[i], dp[i - j] + p[j]);
}
}
cout << dp[N];
return 0;
}
마지막 문제에서 점화식을 세우는데 1, 2, 3 처럼 3값만 비교하면 되는 줄 알고 좀 헤멨다
문제를 잘 읽을 것!
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.