취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24956번 문제인 나는 정말 휘파람을 못 불어이다.
문제는 아래 링크를 확인하자.

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

문자열의 다음 문자로 W, H 또는 E가 나올 때마다 W, WH, WHE와 "유사 휘파람 문자열"을 이루는 부분수열이 새로이 몇 가지 만들어질 수 있는지를 이용하여 계산해내자.

예를 들어 다음 문자로 E가 나오면 완성된 "유사 휘파람 부분 수열"의 개수는 현재 기준 "WHE"의 개수와 기존 "유사 휘파람 부분 수열"의 개수만큼 증가하고 "WHE"의 개수는 현재 기준 "WH"의 개수만큼 증가한다.

아래는 제출한 소스코드이다.

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

unsigned int dp[4];

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

	int slen; string s; cin >> slen >> s;
	for (auto& l : s) {
		if (l == 'E') {
			dp[3] += dp[3] + dp[2];
			while (dp[3] > 1000000006) dp[3] -= 1000000007;
			dp[2] += dp[1];
			if (dp[2] > 1000000006) dp[2] -= 1000000007;
		}
		else if (l == 'H') {
			dp[1] += dp[0];
			if (dp[1] > 1000000006) dp[1] -= 1000000007;
		}
		else if (l == 'W') {
			dp[0]++;
		}
	}

	cout << dp[3];
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24955번 문제인 숫자 이어 붙이기이다.
문제는 아래 링크를 확인하자.

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

평범한 BFS를 하며 숫자를 이어붙여가는 문제이다.

숫자를 길게 이어붙이면 정수로 연산하기 귀찮아지니, 숫자를 이어붙일 때마다 to_string과 stoull을 이용하여 답을 저장해나가자. (정답으로 출력해야하는 나머지값은 일정하게 유지된다.)

1,000,000,007과 1,000,000,000을 이어붙인 10,000,000,001,000,000,000은 2^63을 넘지만 2^64은 넘지 않으므로 stoull을 이용해 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

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

int N, Q;
int ss, ee;
string s[1001];
vector<int> G[1001];
int ans[1001];
int visited[1001];

void bfs() {
	memset(ans, 0, sizeof(ans));
	memset(visited, 0, sizeof(visited));
	queue<int> que;
	que.push(ss);
	visited[ss] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		ans[cur] = stoull(to_string(ans[cur]) + s[cur]) % 1000000007;
		for (auto node : G[cur]) {
			if (visited[node] == 0) {
				visited[node] = 1;
				ans[node] = ans[cur];
				que.push(node);
			}
		}
	}

	cout << ans[ee] << '\n';
}

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

	cin >> N >> Q;
	for (int i = 1; i <= N; i++) cin >> s[i];
	for (int i = 1; i < N; i++) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	while (Q--) {
		cin >> ss >> ee;
		bfs();
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24954번 문제인 물약 구매이다.
문제는 아래 링크를 확인하자.

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

물약을 사는 순서 10!가지 전체를 완전탐색해보자.

글쓴이는 이 문제에서는 충분한 시간여유가 있을 것이라 생각해 각 탐색단계에서의 현재 물약가격 정보를 벡터에 담아 다음 탐색단계에 복사해 넘겨주었다.

아래는 제출한 소스코드이다.

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

int N;
int ans = 1000000007;
vector<pair<int,int>> discount[10];

void func(vector<int> vec, int total, int cnt) {
	if (cnt == N) {
		ans = min(ans, total);
		return;
	}
	cnt++;
	for (int i = 0; i < N; i++) {
		if (vec[i] > 0) {
			auto tmp = vec;
			tmp[i] = 0;
			for (auto p : discount[i]) {
				if (tmp[p.first] > 0) {
					tmp[p.first] = max(1, tmp[p.first] - p.second);
				}
			}
			func(tmp, total + vec[i], cnt);
		}
	}
}

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

	cin >> N;
	vector<int> price(N);
	for (int i = 0; i < N; i++) cin >> price[i];

	for (int i = 0; i < N; i++) {
		int Q; cin >> Q;
		while (Q--) {
			int x, y; cin >> x >> y;
			discount[i].emplace_back(make_pair(x - 1, y));
		}
	}

	func(price, 0, 0);

	cout << ans;
}