Feel Coding

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

#include <iostream>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		int total = 0;
		int price;
		cin >> price;
		total += price;
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			int num, cost;
			cin >> num >> cost;
			total += (num * cost);
		}
		cout << total << '\n';
	}
	return 0;
}

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

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (a > 10) {
			a = (a + 5) / 10 * 10;
		}
		if (a > 100) {
			a = (a + 50) / 100 * 100;
		}
		if (a > 1000) {
			a = (a + 500) / 1000 * 1000;
		}
		if (a > 10000) {
			a = (a + 5000) / 10000 * 10000;
		}
		if (a > 100000) {
			a = (a + 50000) / 100000 * 100000;
		}

		if (a > 1000000) {
			a = (a + 500000) / 1000000 * 1000000;
		}
		if (a > 10000000) {
			a = (a + 5000000) / 10000000 * 10000000;
		}
		cout << a << '\n';
	}
	return 0;
}

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

그냥 LIS(Longest Increasing Sequence)를 구하면 된다.

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

int main() {
	int n;
	cin >> n;
	vector<int> boxes(n);
	for (int i = 0; i < n; i++) {
		cin >> boxes[i];
	}
	int maxBox = 0;
	vector<int> dp(n);
	dp[0] = 1;
	for (int i = 1; i < n; i++) {
		int maxDp = 0;
		for (int j = 0; j < i; j++) {
			if (dp[j] > maxDp && boxes[j] < boxes[i]) {
				maxDp = dp[j];
			}
		}
		dp[i] = maxDp + 1;
		if (dp[i] > maxBox)
			maxBox = dp[i];
	}
	cout << maxBox;
	return 0;
}

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

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

int main() {
	while (true) {
		string s;
		cin >> s;
		if (s == "#") {
			break;
		}
		int count = 0;
		for (int i = 0; i < s.size() - 1; i++) {
			if (s[i] == '1')
				count++;
		}
		if (s[s.size() - 1] == 'e') {
			if (count % 2 == 0) {
				s[s.size() - 1] = '0';
			}
			else {
				s[s.size() - 1] = '1';
			}
		}
		else {
			if (count % 2 == 0) {
				s[s.size() - 1] = '1';
			}
			else {
				s[s.size() - 1] = '0';
			}
		}
		cout << s << '\n';
	}
	return 0;
}

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

동적계획법 문제이다. 동적계획법 문제는 점화식만 잘 세우면 된다.

나는 일단 4까지는 노가다로 구한 뒤 규칙을 찾았다.

점화식은

dp[i] = 2 * dp[i - 1] + dp[i - 2]

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

int main() {
	int n;
	cin >> n;
	vector<int> dp(n + 1);
	dp[0] = 1;
	dp[1] = 3;
	for (int i = 2; i <= n; i++) {
		dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % 9901;
	}
	cout << dp[n];
	return 0;
}

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

동적계획법으로 풀 수 있다.

아래 표 dp의 k행 n열은 숫자 k개를 가지고 n을 만들 수 있는 경우의 수이다.

3행 4열을 예로 들면

dp[3][4]는 3가지 수로 4를 만들 수 있는 방법의 개수인데 4는 0+4, 1+3, 2+2, 3+1, 4+0으로 나타낼 수 있다.

그런데 3행을 채울 당시에는 2행까지만 채워있으니 2행까지 구해놓은 것들을 가지고 3행을 구하면 된다.

0+4는 dp[1][0]*dp[2][4]로 표현 가능하고

(dp[1][0]은 1가지 수로 0을 만들 수 있는 방법의 개수, dp[2][4]는 2가지 수로 4를 만들 수 있는 방법의 개수)

1+3은 dp[1][1]*dp[2][3]으로 표현 가능하고

(dp[1][1]은 1가지 수로 1을 만들 수 있는 방법의 개수, dp[2][3]은 2가지 수로 3을 만들 수 있는 방법의 개수)

2+2는 dp[1][2]*dp[2][2]로 표현 가능하고

(dp[1][2]는 1가지 수로 2를 만들 수 있는 방법의 개수, dp[2][2]는 2가지 수로 2를 만들 수 있는 방법의 개수)

3+1은 dp[1][3]*dp[2][1]으로 표현 가능하고

(dp[1][3]은 1가지 수로 3을 만들 수 있는 방법의 개수, dp[2][1]는 2가지 수로 1을 만들 수 있는 방법의 개수)

4+0은 dp[1][4]*dp[2][0]으로 표현 가능하다.

(dp[1][4]는 1가지 수로 4를 만들 수 있는 방법의 개수, dp[2][0]는 2가지 수로 0를 만들 수 있는 방법의 개수)

즉, dp[3][4] = dp[1][0]*dp[2][4] + dp[1][1]*dp[2][3] + dp[1][2]*dp[2][2] + dp[1][3]*dp[2][1] + dp[1][4]*dp[2][0] 이다.

그런데 1행 즉 K가 1일 때에는 항상 값이 1이므로 1행의 1은 굳이 안 곱해줘도 된다.

따라서  dp[3][4] = dp[2][4] + dp[2][3] + dp[2][2] + dp[2][1] + dp[2][0] 이다.

점화식은 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + dp[i - 1][j - 2] + dp[i - 1][j - 3] + ... + dp[i - 1][0] 으로 표현할 수 있다.

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<vector<int>> dp(k + 1, vector<int>(n + 1));
	for (int i = 0; i <= n; i++) {
		dp[1][i] = 1;
	}
	for (int i = 2; i <= k; i++) {
		dp[i][0] = 1;
	}
	for (int i = 2; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
			for (int c = 0; c <= j; c++) {
				dp[i][j] = (dp[i][j] + dp[i - 1][c]) % 1000000000;
			}
		}
	}
	cout << dp[k][n];
	return 0;
}

오버플로우가 나지 않게 중간중간 1000000000으로 나눠줘야 한다.

이 코드를 제출하니 12ms가 나왔다.

다음은 개선된 코드이다.

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> dp(n + 1, 1);
	for (int i = 2; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
				dp[j] = (dp[j - 1] + dp[j]) % 1000000000;
		}
	}
	cout << dp[n];
	return 0;
}

이렇게 일차원 배열로도 풀 수 있다.

여기에서 쓰는 점화식은 더 간단하다.

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]이다. 그런데 이것을 일차원 배열로 바꾼 코드이다.

이 방법으로 제출하니 0ms가 걸렸다.

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

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

int main() {
	int n;
	cin >> n;
	vector<int> v(3);
	vector<int> minDp(3);
	vector<int> maxDp(3);
	for (int i = 0; i < 3; i++) {
		cin >> v[i];
		minDp[i] = v[i];
		maxDp[i] = v[i];
	}
	
	for (int i = 1; i < n; i++) {
		cin >> v[0] >> v[1] >> v[2];
		int a1 = minDp[0];
		int b1 = minDp[1];
		int c1 = minDp[2];
		int a2 = maxDp[0];
		int b2 = maxDp[1];
		int c2 = maxDp[2];
		minDp[0] = (min(a1 + v[0], b1 + v[0]));
		minDp[1] = (min(min(a1 + v[1], b1 + v[1]), c1 + v[1]));
		minDp[2] = (min(b1 + v[2], c1 + v[2]));
		maxDp[0] = (max(a2 + v[0], b2 + v[0]));
		maxDp[1] = (max(max(a2 + v[1], b2 + v[1]), c2 + v[1]));
		maxDp[2] = (max(b2 + v[2], c2 + v[2]));
	}
	
	int minSum = min(min(minDp[0], minDp[1]), minDp[2]);
	int maxSum = max(max(maxDp[0], maxDp[1]), maxDp[2]);
	cout << maxSum << " " << minSum;
	return 0;
}

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

LIS(Longest Increasing Sequence)를 구하고 N에서 LIS를 빼주면 된다.

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

int main() {
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	vector<int> dp(n);
	dp[0] = 1;
	int lis = 0;
	for (int i = 1; i < n; i++) {
		int maxDp = 0;
		for (int j = 0; j < i; j++) {
			if (dp[j] > maxDp && v[j] < v[i]) {
				maxDp = dp[j];
			}
		}
		dp[i] = maxDp + 1;
		if (dp[i] > lis)
			lis = dp[i];
	}
	cout << n - lis;
	return 0;
}

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

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		int n, cost;
		cin >> n;
		vector<int> coin(n);
		for (int i = 0; i < n; i++) {
			cin >> coin[i];
		}
		cin >> cost;
		vector<vector<int>> dp(n, vector<int>(cost + 1));
		for (int i = 0; i <= cost; i++) {
			if (i % coin[0] == 0)
				dp[0][i] = 1;
		}
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= cost; j++) {
				for (int c = 0; c <= j; c += coin[i]) {
						dp[i][j] += dp[i - 1][j - c];	
				}
			}
		}
		cout << dp[n - 1][cost] << '\n';
	}
	return 0;
}

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

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

vector<vector<int>> v;
vector<vector<int>> dp;
int n;

int dfs(int i, int j) {
	bool flag = false;
	if (dp[i][j] != 0) return dp[i][j];
	int maximum = 0;
	if (i + 1 < n && v[i][j] < v[i + 1][j]) {
		int temp = 1 + dfs(i + 1, j);
		if (temp > maximum) {
			dp[i][j] = temp;
			maximum = temp;
		}
		flag = true;
	}
	if (i - 1 >= 0 && v[i][j] < v[i - 1][j]) {
		int temp = 1 + dfs(i - 1, j);
		if (temp > maximum) {
			dp[i][j] = temp;
			maximum = temp;
		}
		flag = true;
	}
	if (j + 1 < n && v[i][j] < v[i][j + 1]) {
		int temp = 1 + dfs(i, j + 1);
		if (temp > maximum) {
			dp[i][j] = temp;
			maximum = temp;
		}
		flag = true;
	}
	if (j - 1 >= 0 && v[i][j] < v[i][j - 1]) {
		int temp = 1 + dfs(i, j - 1);
		if (temp > maximum) {
			dp[i][j] = temp;
			maximum = temp;
		}
		flag = true;
	}
	if (!flag) {
		dp[i][j] = 1;
	}
	return dp[i][j];
}

int main() {
	cin >> n;
	v = vector<vector<int>>(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
		}
	}
	int maxDp = 0;
	dp = vector<vector<int>>(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dfs(i, j);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dp[i][j] > maxDp) maxDp = dp[i][j];
		}
	}
	cout << maxDp;
	return 0;
}