다이나믹 프로그래밍 문제

1. 1,2,3 더하기 5

문제 : https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int m;
	cin >> m;
	int l = 100000;
	long long mod = 1000000009;
	vector<vector<int>> d;
	d.assign(l+1, vector<int>(4));

	// 초기화
	d[1][1] = 1, d[1][2] = 0, d[1][3] = 0; 
	d[2][1] = 0, d[2][2] = 1, d[2][3] = 0;
	d[3][1] = 1, d[3][2] = 1, d[3][3] = 1;

	// 처리
	for (int i = 4; i <= l; i++) {
		d[i][1] = (d[i - 1][2] + d[i - 1][3]) % mod; // 1 더해주기
		d[i][2] = (d[i - 2][1] + d[i - 2][3]) % mod; // 2 더해주기
		d[i][3] = (d[i - 3][1] + d[i - 3][2]) % mod; // 3 더해주기
	}

	// 반복처리
	for (int cnt = 0; cnt < m; cnt++) {
		int n;
		cin >> n;
		// 형 변환 통해 오버플로 방지
		long long ans = (long long)d[n][1] + (long long)d[n][2] + (long long)d[n][3];
		ans = ans % mod;
		cout << ans << endl;
	}
}

2. 쉬운 계단수

문제 : https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int n;
	long long ans = 0;
	long long mod = 1000000000;
	cin >> n;

	vector<vector<int>> d;
	d.assign(n + 1, vector<int>(10));

	// 초기화
	for (int i = 1; i <= 9; i++)
		d[1][i] = 1;

	// 계산
	for (int i = 2; i <= n; i++) {
		d[i][0] = d[i - 1][1];
		d[i][9] = d[i - 1][8];
		for (int j = 1; j <= 8; j++) {
			d[i][j] = d[i - 1][j - 1] + d[i - 1][j + 1];
			d[i][j] %= mod;
		}
	}

	// 정답
	for (int i = 0; i <= 9; i++)
		ans += (long long)d[n][i];
	cout << ans % mod;

	return 0;
}

3. 오르막수

문제 : https://www.acmicpc.net/problem/11057

11057번: 오르막 수

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int n;
	int ans = 0;
	int mod = 10007;
	cin >> n;

	vector<vector<int>> d;
	d.assign(n + 1, vector<int>(10));

	// 초기화
	for (int i = 0; i <= 9; i++)
		d[1][i] = 1;

	// 계산
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			int temp=0;
			for (int k = j; k <= 9; k++)
				temp += d[i-1][k]; // 이전 마지막 자리 수
			d[i][j] = temp;
			d[i][j] %= mod;
		}
	}

	// 정답
	for (int i = 0; i <= 9; i++)
		ans += d[n][i];
	cout << ans % mod;

	return 0;
}

4. 이친수

문제 : https://www.acmicpc.net/problem/2193

2193번: 이친수

풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	
	vector<vector<long long>> d;
	d.assign(n + 1, vector<long long>(2));

	// 초기화
	d[1][0] = 0, d[1][1] = 1;

	// 처리
	for (int i = 2; i <= n; i++) {
		d[i][0] = d[i - 1][0] + d[i - 1][1];
		d[i][1] = d[i - 1][0];
	}

	// 출력
	cout << d[n][0] + d[n][1];
	return 0;
}

5. 스티커

문제 : https://www.acmicpc.net/problem/9465

9465번: 스티커

풀이

#include <iostream>
#include <vector>
using namespace std;

long long max3(long long, long long, long long);
long long max2(long long, long long);
int main() {
	int cnt,n;
	int l = 100000;
	cin >> cnt;

		
	for (int tmp = 0; tmp < cnt; tmp++) {
		cin >> n;

		// 할당
		vector<vector<long long>> d;
		vector<vector<int>> p;
		d.assign(n + 1, vector<long long>(3));
		p.assign(n + 1, vector<int>(2));

		// 입력 받기
		for (int i = 1; i <= n; i++)
			cin >> p[i][0];
		for (int i = 1; i <= n; i++)
			cin >> p[i][1];

		// 처리(x, 위, 아래)
		d[1][0] = 0, d[1][1] = p[1][0], d[1][2] = p[1][1];
		for (int i = 2; i <= n; i++) {
			d[i][0] = max3(d[i - 1][0], d[i - 1][1], d[i - 1][2]);
			d[i][1] = max2(d[i - 1][0], d[i - 1][2]) + p[i][0]; // 바로앞: 아래, 현재: 위
			d[i][2] = max2(d[i - 1][0], d[i - 1][1]) + p[i][1]; // 바로앞: 위, 현재: 아래
		}
		cout << max3(d[n][0], d[n][1], d[n][2]) << endl;
	}

	return 0;
}

long long max3(long long a, long long b, long long c) {
	if (a >= b)
		if (a >= c)
			return a;

	if (b >= c)
		if (b >= a)
			return b;

	if (c >= a)
		if (c >= b)
			return c;
}

long long max2(long long a, long long b) {
	if (a >= b)
		return a;

	else
		return b;
}

6. 포도주 시식

문제 : https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long max3(long long, long long, long long);
long long max2(long long, long long);

int main() {
	int n;
	cin >> n;

	// 입력
	vector<vector<long long>> d;
	vector<int> p;
	d.assign(n + 1, vector<long long>(3));
	p.assign(n + 1, 0);

	for (int i = 1; i <= n; i++)
		cin >> p[i];
	
	
	// 처리
	for (int i = 1; i <= n; i++) {
		d[i][0] = max3(d[i - 1][0], d[i - 1][1], d[i - 1][2]); // 안마시기
		d[i][1] = d[i - 1][0] + p[i]; // 한잔 마시기(이전에 0잔)
		d[i][2] = d[i - 1][1] + p[i]; // 두잔 째의 경우(이전에 1잔만 가능)
	}
	
	cout << max3(d[n][0], d[n][1], d[n][2]);

}

long long max3(long long a, long long b, long long c) {
	if (a >= b)
		if (a >= c)
			return a;

	if (b >= c)
		if (b >= a)
			return b;

	if (c >= a)
		if (c >= b)
			return c;
}

long long max2(long long a, long long b) {
	if (a >= b)
		return a;

	else
		return b;
}