취미로 코딩하기

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

이번에 볼 문제는 백준 28071번 문제인 승형이의 사탕 사기이다.
문제는 아래 링크를 확인하자.

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

N종류의 사탕상자를 차례대로 읽어나갈 때, dp[m][k]를 이전까지 읽은 사탕상자들을 총 m개 사용해 얻을 수 있는 사탕의 개수 중 K로 나눈 나머지가 k인 값의 최댓값으로 정의하자.

이 때, 새로운 사탕상자의 크기 n을 읽어들였을 때, dp[m][k]를 m이 작은 순서대로 찾아가 각 사탕 개수에 n개의 사탕을 추가해 만들 수 있는 새로운 사탕개수의 값을 이용해 dp[m+1][k'](k'은 새 사탕개수를 K로 나눈 나머지)의 값을 갱신해나가는 것으로 dp배열을 올바르게 갱신해나갈 수 있다. 각 상태에 여러 사탕상자가 아닌 하나의 사탕상자만을 추가해보는 것으로 충분한 이유는 이후에 dp[m+1][k'] 상태에 대하여 다시 사탕상자를 하나 추가해보는 것을 시도하기 때문이다.

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

#include <iostream>
using namespace std;

int N, M, K;
int dp[301][301]; // dp[상자m개][K로 나눈 나머지]: 해당 조건 만족하는 사탕 최댓값

int ans;

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

	cin >> N >> M >> K;
	for (int m = 0; m <= M; m++) {
		for (int k = 0; k < K; k++) {
			dp[m][k] = -1000000007;
		}
	}
	dp[0][0] = 0;

	while (N--) {
		int x; cin >> x;
		for (int m = 0; m < M; m++) {
			for (int k = 0; k < K; k++) {
				int tmp = dp[m][k] + x;
				dp[m + 1][tmp % K] = max(dp[m + 1][tmp % K], tmp);
			}
		}
	}

	for (int m = 1; m <= M; m++) ans = max(ans, dp[m][0]);

	cout << ans;
}

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

이번에 볼 문제는 백준 28070번 문제인 유니의 편지 쓰기이다.
문제는 아래 링크를 확인하자.

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

현재 군대에 있는 친구의 수를 나타내는 변수를 하나 준비하자. 이러한 변수를 이용하면 친구들의 입대시기 s1과 전역시기 s2를 시간순으로 정렬한 다음 시간순으로 살피며 입대와 전역이 일어날 때마다 해당 변수의 값을 바꾸는 것으로 매달 입대한 친구의 수를 알 수 있다. 이를 이용해 가장 많은 친구가 입대해있는 달을 찾아 문제를 해결하자.

같은 달에 입대하는 친구와 전역해서 더이상 군인이 아니게 된 친구가 있는 경우 전역하는 친구를 먼저 처리해 해당 달에 입대한 친구의 수 값이 부풀려지는 순간이 나오지 않게끔 변수를 관리할 수 있다.

입력으로 주어진 YYYY-MM꼴의 문자열은 문자열 자체 기본 대소비교를 통해서도 정렬이 가능하므로 특별한 문자열처리를 하지 않더라도 문제를 충분히 해결할 수 있다!

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

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

int N;
vector<pair<string, int>> vec;
int val, mx; string ans;

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

	cin >> N;
	while (N--) {
		string s1, s2; cin >> s1 >> s2;
		vec.emplace_back(make_pair(s1, -1));
		vec.emplace_back(make_pair(s2, 1));
	}

	sort(vec.begin(), vec.end());

	for (auto& p : vec) {
		val -= p.second;
		if (mx < val) mx = val, ans = p.first;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 28069번 문제인 김밥천국의 계단이다.
문제는 아래 링크를 확인하자.

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

0번 계단에서 각 n번째 계단까지 올라가는 데에 x번 계단 오르기로 올라갈 수 있다면 x보다 큰 횟수 y로도 올라갈 수 있음을 관찰하자. 이는 0번 계단에서 2번 행동을 x와 y의 차만큼 반복하고 x번 계단 오르기를 하는 것으로 가능하다.

위의 관찰을 이용하면 N번 계단까지 필요한 최소 계단 오르기 횟수를 구해 그 값이 K보다 작거나 같은지를 판단하는 것으로 문제를 해결할 수 있다. 최소 계단 오르기 횟수는 각 계단을 노드로, 각 계단에서 이동할 수 있는 계단의 관계를 방향 에지로 갖는 그래프 모델링에서의 BFS를 이용해 구할 수 있다.

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

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

int N, K;
int dist[1000001];

queue<int> que;
void bfs() {
	dist[0] = 1;
	que.push(0);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		int nxt1 = cur + 1, nxt2 = cur + cur / 2;
		if (nxt1 <= 1000001 && !dist[nxt1]) {
			dist[nxt1] = dist[cur] + 1;
			que.push(nxt1);
		}
		if (nxt2 <= 1000001 && !dist[nxt2]) {
			dist[nxt2] = dist[cur] + 1;
			que.push(nxt2);
		}
	}
}

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

	bfs();

	cin >> N >> K;

	if (dist[N] - 1 <= K) cout << "minigimbob";
	else cout << "water";
}

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

이번에 볼 문제는 백준 28068번 문제인 I Am Knowledge이다.
문제는 아래 링크를 확인하자.

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

각 책을 (a,b)와 같이 나타낸다면, 해당 책은 마법사의 즐거움이 a 이상일 때 읽어 즐거움을 b-a만큼 증가시켜줄 수 있다. (단, b-a가 음수이면 a-b만큼 감소한다.) 모든 책을 읽는 방법이 존재한다면 순서를 적절히 조절해 '책을 읽기 전과 비교했을 때 읽은 뒤 즐거움이 증가하는 책'들을 모두 읽고 그렇지 않은 책들을 마저 읽어 모든 책을 읽을 수도 있음을 관찰하자.

읽은 뒤 즐거움이 증가하는 책들을 조건을 만족하도록 전부 읽는 것이 가능한지는 그러한 책들을 a값을 기준으로 오름차순 정렬했을 때 이 책들을 그 순서대로 읽어나갈 수 있는지를 확인하는 것으로 해낼 수 있다.

읽은 뒤 즐거움이 감소하는 책들을 차례대로 읽을 수 있는지를 생각해보자. 만약 그러한 방법이 존재한다면 모든 책을 다 읽었을 때의 최종 즐거움 값은 (모든 b의 값의 합) - (모든 a의 값의 합)이 될 것이다. 이 즐거움 값에서 시작해 즐거움이 감소하는 책을 읽어나가던 과정을 거꾸로 실행해나가는 것은 '현재 즐거움 값이 b 이상일 때 읽어 즐거움을 a-b(>0)만큼 증가시키는' 책을 읽어나가는 것으로 생각할 수 있다. 이것이 앞선 문단의 경우와 동일함을 관찰하면 이 또한 같은 방법으로 해결할 수 있음을 알 수 있다.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int N;
vector<pair<int, int>> vec1, vec2;
ll val1, val2;

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

	cin >> N;
	while (N--) {
		int a, b; cin >> a >> b;
		val1 += (b - a);
		if (a > b) vec1.emplace_back(make_pair(b, a - b));
		else vec2.emplace_back(make_pair(a, b - a));
	}

	sort(vec1.begin(), vec1.end());
	sort(vec2.begin(), vec2.end());

	for (auto& p : vec1) {
		if (val1 < p.first) {
			cout << 0;
			return 0;
		}
		val1 += p.second;
	}

	for (auto& p : vec2) {
		if (val2 < p.first) {
			cout << 0;
			return 0;
		}
		val2 += p.second;
	}

	cout << 1;
}

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

이번에 볼 문제는 백준 28067번 문제인 기하가 너무 좋아이다.
문제는 아래 링크를 확인하자.

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

가능한 세 점의 쌍은 순서쌍 \(((a,d),(b,e),(c,f))\)와 같이 나타낼 수 있다. 각 변수 \(a,b,c,d,e,f\)는 0 이상 10 이하이므로 이와 같은 모든 순서쌍의 개수는 \(11^6=1771561\)가지이다.

각 순서쌍에 대하여 해당 순서쌍이 (1) 삼각형을 나타내는지 확인 후 (2) 해당 삼각형과 대응되는, 즉 합동이면 같은 값을 갖고 그렇지 않다면 다른 값을 갖는 변수를 이용해 개수를 세어 문제를 해결하자.

(2)의 판단 기준으로 글쓴이는 변의 길이를 이용한다. 두 삼각형의 세 변의 길이가 같다는 것과 두 삼각형은 합동(SSS합동)임이 동치임은 잘 알려져있다. 이에 따라 두 삼각형의 세 변의 길이'의 제곱'이 같은 것과 두 삼각형이 합동인 것은 동치라고 말할 수 있다. 따라서 위에서 정의한 변수 \(a,b,c,d,e,f\)를 이용하면 세 변의 길이의 제곱을 간단히 계산할 수 있고, 이들을 크기순으로 나열하면 합동인 두 삼각형은 같은 나열을 갖게 될 것임을 알 수 있다. 이와 같은 나열의 가짓수를 계산해 문제를 해결하자.

글쓴이는 해당 나열을 200진법의 정수로 생각(문제 제약조건상 변의 길이의 제곱은 1 이상 200 이하의 값임을 이용)해 해당 나열을 정수에 다시 대응시켜 문제를 해결하였다.

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

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

int N, M;
bool visited[8000001];
int cnt;

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

	cin >> N >> M;
	for (int a = 0; a <= N; a++) {
		for (int b = a; b <= N; b++) {
			for (int c = b; c <= N; c++) {
				for (int d = 0; d <= M; d++) {
					for (int e = 0; e <= M; e++) {
						for (int f = 0; f <= M; f++) {
							if ((b - a) * (f - d) == (e - d) * (c - a)) continue; // 삼각형이 아님

							int dx1 = b - a, dx2 = c - b, dx3 = a - c, dy1 = e - d, dy2 = f - e, dy3 = d - f;
							dx1 *= dx1, dx2 *= dx2, dx3 *= dx3, dy1 *= dy1, dy2 *= dy2, dy3 *= dy3;
							int X = dx1 + dy1, Y = dx2 + dy2, Z = dx3 + dy3;
							vector<int> vec = { X - 1,Y - 1,Z - 1 };
							sort(vec.begin(), vec.end());

							int val = vec[0] * 40000 + vec[1] * 200 + vec[2];
							if (visited[val]) continue;
							visited[val] = 1;
							cnt++;
						}
					}
				}
			}
		}
	}

	cout << cnt;
}

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

이번에 볼 문제는 백준 28066번 문제인 타노스는 요세푸스가 밉다이다.
문제는 아래 링크를 확인하자.

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

문제에서 주어지는 내용을 직접 시뮬레이션하는 코드를 작성하자. 큐(queue) 자료구조에 1부터 N까지의 청설모를 차례대로 넣고, 이번 과정에서 다룰 K마리를 큐에서 접근하면 주어진 내용을 빠르게 시뮬레이션할 수 있다.

구체적으로, 큐의 첫 번째 원소가 "첫 번째 청설모"일 때, 첫 번째 청설모를 저장한 다음 큐에서 K마리(남은 청설모가 K보다 적다면 남은 마릿수)만큼 큐에서 청설모를 제거하고 첫 번째 청설모를 큐에 새로 추가하면 다음 "첫 번째 청설모"가 큐의 맨 앞에 있는 상태로 만들 수 있다. 이를 반복해 문제를 해결하자.

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

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

int N, K;
queue<int> que;

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

	cin >> N >> K;
	for (int i = 1; i <= N; i++) que.push(i);

	while (que.size() > 1) {
		int kp = que.front();
		int itercnt = min(K, (int)que.size());
		for (int i = 0; i < itercnt; i++) que.pop();
		que.push(kp);
	}

	cout << que.front();
}