Codetesing의 코딩공부

아주 쉬운문제로 딱히 알고리즘이 필요하지 않았다.

N <= 10^6이므로 O(N)으로 풀어도 통과할꺼라 예상하였다.따라서 반복문을 이용해 알고리즘 없이 풀었다.

#include<iostream>

using namespace std;

#define DIV 1000000007

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int K, P, N; cin >> K >> P >> N;

	long long ans = K;

	for (int i = 0; i < N; i++) {
		ans *= P;
		ans %= DIV;
	}

	cout << ans << '\n';

	return 0;
}

DP를 이용한 문제로 크게 어렵지 않았다.

A, B의 모든 단계의 값을 구해 최소값을 가지는식으로 풀었다.

A(i - 1)에서 A(i)와 B(i - 1)에서 A(i)의 최소 비교를 하여 작은값을 구한다.

흔한 최소 소요값 문제이며 backtracking과 DP중 DP가 빠를것 같아 DP로 풀었다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N; cin >> N;
    vector<int> A(N, 0);
    vector<int> B(N, 0);
    vector<int> WA(N + 1, 0);
    vector<int> WB(N + 1, 0);
    vector<vector<int>> DP(N, vector<int>(2, 0));

    for(int i = 0; i < N - 1; i++)
        cin >> A[i] >> B[i] >> WB[i + 1] >> WA[i + 1];
    cin >> A[N - 1] >> B[N - 1];

    DP[0][0] = A[0];
    DP[0][1] = B[0];

    for(int i = 1; i < N; i++) {
        DP[i][0] = min(DP[i - 1][0], DP[i - 1][1] + WA[i]) + A[i];
        DP[i][1] = min(DP[i - 1][1], DP[i - 1][0] + WB[i]) + B[i];
    }

    int ans = min(DP[N - 1][0], DP[N - 1][1]);

    cout << ans << '\n';

	return 0;
}

난이도 치고는 쉬웠던 문제이다.

처음엔 그래프 완전탐색 문제로 알았으나 그럴 필요 없이 각 node에 연결된 부분만 확인하면 되었다.

그렇기 때문에 2중 반복문을 사용해 쉽게 해결했다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, M; cin >> N >> M;
	
	vector<int> W(N + 1, 0);
	vector<vector<int>> G(N + 1, vector<int>());
	for (int i = 1; i <= N; i++)
		cin >> W[i];

	int a, b;
	for (int i = 1; i <= M; i++)
	{
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		int max_val = W[i];
		bool flag = true;

		for (int j = 0; j < G[i].size(); j++)
			if (max_val <= W[G[i][j]])
			{
				flag = false;
				break;
			}

		if (flag)
			ans++;
	}

	cout << ans << '\n';

	return 0;
}

Greedy 문제이다.

Greedy라 칭하기엔 너무 쉬운 문제였지만 알고리즘만 놓고 본다면 Greedy에 속한다.

보통 자를수 없게 나오는데 자를수 있어서 쉽게 풀었다.

어려움 없이 가치 순 대로 정렬한 후, W를 빼면서 최대 가치를 구하면 된다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

typedef struct jewl {
	int M;
	int P;
} jewl;

bool compare(jewl a, jewl b) {
	return a.P > b.P;
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int W, N; cin >> W >> N;

	vector<jewl> arr;

	int a, b;
	for(int i = 0; i < N; i++) {
		cin >> a >> b;

		arr.push_back({a, b});
	}

	sort(arr.begin(), arr.end(), compare);

	int val = 0;
	for(int i = 0; i < N; i++) {
		if(W >= arr[i].M) {
			val += arr[i].M * arr[i].P;
			W -= arr[i].M;
		}
		else {
			val += W * arr[i].P;
			W = 0;
		}

		if(W == 0)
			break;
	}

	cout << val << '\n';

	return 0;
}

크게 어렵지 않은 구현 문제였다.

끝나는 시간을 오름차순 정렬하여 구하면 되는 문제이다.

끝나는 시간에 초점을 맞춰 시뮬레이션 해보면 쉽게 풀린다.

#include<iostream>
#include<algorithm>
#include<vector>

#define MAX 1000000001

using namespace std;

typedef struct lect{
	int s;
	int e;
}lect;

bool compare(lect a, lect b) {
	return a.e < b.e;
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N; cin >> N;
	vector<lect> arr;

	for(int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		arr.push_back({a, b});
	}

	sort(arr.begin(), arr.end(), compare);

	int cur = arr[0].e;
	int cnt = 1;

	for(int i = 1; i < N; i++) {
		if(cur <= arr[i].s)
		{
			cur = arr[i].e;
			cnt++;
		}
	}

	cout << cnt << '\n';

	return 0;
}