오늘의 문제
1463 1로 만들기
9095 1, 2, 3 더하기
2579 계단 오르기
1149 RGB 거리
11726 2xn 타일링
11659 구간 합 구하기 4
12852 1로 만들기 2

1463 1로 만들기

코드

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[1000002];

int main() {
	cin >> n;

	fill(dp, dp + 1000002, 1000000);
	dp[n] = 0;
	for (int i = n; i >= 1; i--) {
		if (i % 3 == 0) dp[i / 3] = min(dp[i / 3], dp[i] + 1);
		if (i % 2 == 0) dp[i / 2] = min(dp[i / 2], dp[i] + 1);
		dp[i - 1] = min(dp[i - 1], dp[i] + 1);
	}
	cout << dp[1];
}

한 세 번 푼 것 같다.

9095 1, 2, 3 더하기

코드

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[12];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	dp[0] = 1; dp[1] = 1; dp[2] = 2;

	for (int i = 3; i < 12; i++) {
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
	}

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		cout << dp[a] << "\n";
	}
}

이것도 두 번 정도 풀었던 것 같다.

2579 계단 오르기

코드

#include <bits/stdc++.h>
using namespace std;

int n;
int stair[302], dp[302];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> stair[i];
	}

	dp[1] = stair[0]; dp[2] = dp[1] + stair[1];
	for (int i = 3; i <= n; i++) {
		dp[i] = max(stair[i - 2] + dp[i - 3], dp[i - 2]) + stair[i - 1];
	}
	cout << dp[n];
}

1149 RGB 거리

코드

#include <bits/stdc++.h>
using namespace std;

int n;
int house[1002][3], color[1002][3];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> house[i][0] >> house[i][1] >> house[i][2];
	}
	color[0][0] = house[0][0]; color[0][1] = house[0][1]; color[0][2] = house[0][2];
	for (int i = 1; i < n; i++) {
		color[i][0] = min(color[i - 1][1], color[i - 1][2]) + house[i][0];
		color[i][1] = min(color[i - 1][0], color[i - 1][2]) + house[i][1];
		color[i][2] = min(color[i - 1][0], color[i - 1][1]) + house[i][2];
	}
	cout << min({ color[n - 1][0], color[n - 1][1], color[n - 1][2] });
}

11726 2xn 타일링

코드

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[1002];

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

11659 구간 합 구하기 4

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
int num[100005], dp[100005];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		dp[i] = dp[i - 1] + num[i - 1];
	}
	while (m--) {
		int i, j;
		cin >> i >> j;
		cout << dp[j] - dp[i - 1] << "\n";
	}
}

12852 1로 만들기 2

코드

#include <bits/stdc++.h>
using namespace std;

int n, dp[1000005];
int bf[1000005];

int main() {
	cin >> n;
	dp[1] = 0;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + 1;
		bf[i] = i - 1;
		if (i % 3 == 0) {
			if (dp[i] > dp[i / 3] + 1) {
				dp[i] = dp[i / 3] + 1;
				bf[i] = i / 3;
			}
			
		}
		if (i % 2 == 0) {
			if (dp[i] > dp[i / 2] + 1) {
				dp[i] = dp[i / 2] + 1;
				bf[i] = i / 2;
			}
		}
	}
	cout << dp[n] << "\n";
	int now = n;
	while (now != 0) {
		cout << now << " ";
		now = bf[now];
	}
}

1463번과 반대로 1에서 시작하여 n까지 커지기. 이 방식이 메모리 초기화를 안 해도 되서 더 나은 것 같다.