굳건하게

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

[ 알고리즘풀이 ]

1. 현재 주유소 가격보다 싼 가격의 주유소가 앞으로 있는지 순회합니다.

2. 있다면 그 주유소까지만 현재 주유소에서 기름을 채워서 이동합니다.

3. 없다면 끝까지 현재 주유소에서 기름을 채워서 이동합니다.

#include<iostream>

using namespace std;

int N, length[100000] = {}, price[100000] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N - 1; i++)
		cin >> length[i];
	for (int i = 0; i < N; i++)
		cin >> price[i];
	
	long long ans = 0;
	int i = 0;
	while(i < N){
		int j = i + 1;
		long long l = 0;
		while (j < N) {
			l += length[j - 1];
			if (price[i] > price[j])
				break;
			j++;
		}
		ans += 1LL * l * price[i];
		i = j;
	}
	cout << ans;
}

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

[ 알고리즘풀이 ]

 A진법으로 표현한 수를 10진법으로 돌리고, 다시 그 수를 B진법으로 표현하면 된다.

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int A, B, M, list[25] = {};
	cin >> A >> B >> M;
	for (int i = 0; i < M; i++)
		cin >> list[i];
	
	// A진법 수를 10진법으로
	int temp = 0, mul = 1;
	for (int i = 0; i < M; i++) {
		temp += mul * list[M - 1 - i];
		mul *= A;
	}
	// 10진법으로 표현한 수를 B진법으로
	vector<int> ans;
	while (temp) {
		ans.push_back(temp % B);
		temp /= B;
	}

	for (int i = 0; i < ans.size(); i++)
		cout << ans[ans.size() - 1 - i] << ' ';

	return 0;
}

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

[ 알고리즘풀이 ]

DP[N][M] : N을 M개의 1, 2, 3 의 합으로 표현하는 경우의 수.

→ DP[N][M] = DP[N - 1][M - 1] + DP[N - 2][M - 1] + DP[N - 3][M - 1];

#include<iostream>
#define MOD 1000000009

using namespace std;

int T, N, M, dp[1001][1001] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	dp[1][1] = 1, dp[2][1] = 1, dp[2][2] = 1, dp[3][1] = 1, dp[3][2] = 2, dp[3][3] = 1;
	for (int i = 4; i <= 1000; i++) {
		for (int j = 1; j <= 1000; j++)
			dp[i][j] = ((dp[i - 1][j - 1] + dp[i - 2][j - 1]) % MOD + dp[i - 3][j - 1]) % MOD;
	}
	cin >> T;
	while (T--) {
		cin >> N >> M;
		cout << dp[N][M] << '\n';
	}
	return 0;
}

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

[ 알고리즘풀이 ]

DP[N] : N 을 1, 2, 3의 합으로 대칭을 이루며 표현하는 경우의 수

→ DP[N] = DP[N - 2] + DP[N - 4] + DP[N - 6];

( 기존의 표현 방법에다가 양쪽 끝에 1 , 1 / 2, 2 / 3, 3 을 추가하면 된다. )

#include<iostream>
#define M 1000000009

using namespace std;

int T, N, dp[100001] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	dp[1] = 1, dp[2] = 2, dp[3] = 2, dp[4] = 3, dp[5] = 3, dp[6] = 6;
	for (int i = 7; i <= 100000; i++) {
		dp[i] = ((dp[i - 2] + dp[i - 4]) % M + dp[i - 6]) % M;
	}
	cin >> T;
	while (T--) {
		cin >> N;
		cout << dp[N] << '\n';
	}
}