취미로 코딩하기

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

이번에 볼 문제는 백준 14718번 문제인 용감한 용사 진수이다.
문제는 아래 링크를 확인하자.

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

진수가 스탯을 힘 능력치에 \(X\)만큼 투자할 경우, X 이하의 힘 능력치를 요구하는 병사 중 가장 높은 값으로 X의 값을 바꿔도 상대할 수 있는 병사의 수는 변하지 않음을 관찰하자. 이러한 관찰은 민첩, 지능 등 다른 능력치에도 동일하게 적용된다.

위의 관찰을 통해 가장 효율적으로 스탯을 배분하는 방법은 각 스탯을 병사의 스탯 중 하나의 값으로 투자하는 것임을 알 수 있다. 이러한 스탯 투자방법은 \(N^3\) 가지 존재하고, 각 경우마다 병사 \(K\)명을 상대할 수 있는지의 여부는 300번의 비교를 통해 확인할 수 있다. 이는 이 문제를 해결하기에 충분한 연산 수이다.

위의 내용을 구현한 코드를 제출해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N, K;
int STR[100], DEX[100], INT[100];
int enemy[100][3];
int ans = 1000000007;

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> enemy[i][0] >> enemy[i][1] >> enemy[i][2];
		STR[i] = enemy[i][0], DEX[i] = enemy[i][1], INT[i] = enemy[i][2];
	}

	for (int s = 0; s < N; s++) {
		int& ss = STR[s];
		for (int d = 0; d < N; d++) {
			int& dd = DEX[d];
			for (int i = 0; i < N; i++) {
				int& ii = INT[i];
				int cnt = 0;
				for (int k = 0; k < N; k++) {
					if (ss < enemy[k][0] || dd < enemy[k][1] || ii < enemy[k][2]) continue;
					cnt++;
				}

				if (cnt >= K) ans = min(ss + dd + ii, ans);
			}
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 14717번 문제인 앉았다이다.
문제는 아래 링크를 확인하자.

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

영학이가 들고 있는 패를 제외한 카드들 중 두 카드를 뽑을 경우의 수와 그 경우 중 영학이가 이기는 경우의 수를 구해 문제를 해결할 수 있다. 이 과정에서 같은 수가 적혀있는 두 카드는 서로 다른 카드로 생각해야 함에 유의하자.

두 카드쌍 사이에서 어느 한 카드쌍이 이기는지 판단하는 방법 중 하나는 (1) 두 쌍 모두가 땡인지 (2) 한 쌍만 땡인지 (3) 두 쌍 모두가 끗인지로 경우를 나누어 생각하는 것이다. 각 경우 영학이의 패가 이기는지를 판단해 경우의 수를 세어주자.

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

#include <iostream>
using namespace std;

int card[20] = { 1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10 };
int visited[20];
int X, Y;

int cnt, total;

bool comp(int x, int y) {
	if (X == Y && x == y) return X > x;
	if (X == Y) return 1;
	if (x == y) return 0;
	return (X + Y) % 10 > (x + y) % 10;
}

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

	cin >> X >> Y;
	visited[X * 2 - 2] = visited[Y * 2 - 1] = 1;
	
	for (int i = 0; i < 20; i++) {
		if (visited[i]) continue;
		for (int j = i + 1; j < 20; j++) {
			if (visited[j]) continue;
			total++;
			if (comp(card[i], card[j])) cnt++;
		}
	}

	cout << fixed;
	cout.precision(3);

	cout << (double)cnt / total;
}

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

이번에 볼 문제는 백준 14716번 문제인 현수막이다.
문제는 아래 링크를 확인하자.

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

주어진 현수막의 글자는 현수막을 구성하는 각 부분 중 글자를 나타내는 부분들을 노드로, 여덟 방향 중 한 방향으로 인접해 서로 이어져있는 부분들 사이의 관계를 에지로 생각해 그래프로 모델링할 수 있다.

글자의 개수는 위에서 모델링한 그래프의 connected component와 같으므로 그 값을 구해 문제를 해결할 수 있다. 글쓴이는 dfs를 이용해 계산했다.

탐색 과정에서 아래 코드의 dx와 dy와 같은 배열을 이용하는 것으로 구현을 더욱 간단하게 할 수 있다.

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

#include <iostream>
using namespace std;

int R, C;
int board[252][252];
int dx[8] = { 1,1,1,0,-1,-1,-1,0 };
int dy[8] = { 1,0,-1,-1,-1,0,1,1 };

void dfs(int r, int c) {
	board[r][c] = 0;
	for (int i = 0; i < 8; i++) {
		int rr = r + dx[i], cc = c + dy[i];
		if (board[rr][cc]) dfs(rr, cc);
	}
}

int cnt;

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

	cin >> R >> C;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) cin >> board[r][c];
	}

	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			if (board[r][c]) cnt++, dfs(r, c);
		}
	}

	cout << cnt;
}

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

이번에 볼 문제는 백준 28353번 문제인 고양이 카페이다.
문제는 아래 링크를 확인하자.

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

먼저 고양이들을 무게를 기준으로 정렬하자. 그리고 무거운 고양이부터 한 마리씩 살피면서, 해당 고양이와 현재 남아있는 가장 가벼운 고양이가 무게의 합이 K 이하가 되는 짝을 이룰 수 있다면 새 짝을 하나 이루고 그렇지 않다면 해당 고양이를 제외하는 작업을 반복하는 그리디 전략으로 문제를 해결할 수 있다.

위의 전략이 올바른 답을 항상 찾을 수 있는 이유를 생각해보자. 만약 X개의 고양이 쌍을 구성할 수 있다면 각 쌍을 구성하는 두 고양이 중 가벼운 고양이를 선택되지 않은 더 가벼운 고양이로 바꾸는 작업을 반복하는 것으로 가장 가벼운 X마리의 고양이가 서로 다른 쌍에 들어있는 고양이 쌍 구성을 찾을 수 있음을 관찰하자. 따라서 X개의 고양이 쌍을 구성할 수 있다면 가장 가벼운 고양이 X마리들이 서로 다른 쌍에 들어가게 할 수 있어야 한다. 이 때 최대한 많은 고양이 쌍을 만들기 위해서는 가벼운 고양이일수록 더 무거운 고양이와 쌍을 구성하게 해야 함은 쉽게 관찰할 수 있다. 

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

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

int N, K;
int L, R;
int arr[5000];

int ans;

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> arr[i];

	sort(arr, arr + N);

	R = N - 1;
	while (L < R) {
		if (arr[L] + arr[R] > K)R--;
		else ans++, L++, R--;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 10193번 문제인 Word Swap이다.
문제는 아래 링크를 확인하자.

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

각 소문자 'a-z'는 아스키코드에 97번부터 122번까지 차례대로 배정되어 있음을 상기하자. 따라서 문제에서 구하고자하는 값은 첫번째 문자열의 \(i\)번째 문자 \(S1_i\)와 두번째 문자열의 \(i\)번째 문자 \(S2_i\)의 아스키코드 값의 차, 즉 \(S1_i - S2_i\)의 값들을 모두 더하는 것으로 계산할 수 있다. 글쓴이는 위의 연산 순서를 바꿔 초기값이 0인 변수에 \(S1\)을 구성하는 문자들의 아스키코드 값을 모두 더하고 \(S2\)를 구성하는 문자들의 아스키코드 값을 모두 빼는 방식으로 구현하였다.

지문에 나와있듯이 정확한 출력 형식을 확인하기 위해 제출 창에서 Java 코드를 꼭 열어보도록 하자. 위에서 계산한 값이 음수일 경우 "earned"가 아닌 "cost"를 이용한 별도의 출력형식이 지정되어 있음을 알 수 있다.

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

#include <iostream>
using namespace std;

int T;

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

	cin >> T;
	while (T--) {
		int ans = 0;
		string s1, s2; cin >> s1 >> s2;
		for (auto& l : s1) ans += l;
		for (auto& l : s2) ans -= l;

		if (ans > 0) cout << "Swapping letters to make " << s1 << " look like " << s2 << " earned " << ans << " coins.\n";
		else if (ans < 0) cout << "Swapping letters to make " << s1 << " look like " << s2 << " cost " << -ans << " coins.\n";
		else cout << "Swapping letters to make " << s1 << " look like " << s2 << " was FREE.\n";
	}
}

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

이번에 볼 문제는 백준 13322번 문제인 접두사 배열이다.
문제는 아래 링크를 확인하자.

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

주어진 문자열의 접두사들의 모임은 \(s\)의 0번째 문자부터 \(i\)번째 문자까지의 부분문자열 \(s_i\)들의 모임과 같음을 관찰하자. 또한, \(s_i\)와 \(s_j\) (단, \(i<j\)에 대하여 \(s_j\)의 앞 \(i+1\)글자로 이루어진 문자열은 \(s_i\)와 항상 같으므로 사전순을 기준으로 \(s_i<s_j\)가 항상 성립한다. 즉, \(i<j\)이면 \(s_i<s_j\)가 성립한다.

따라서 문자열의 길이를 \(N\)이라 할 때 0부터 \(N-1\)까지의 정수를 차례대로 출력하는 것으로 문제를 해결할 수 있다.

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

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

string s; int slen;

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

	cin >> s;
	slen = s.length();

	for (int i = 0; i < slen; i++) cout << i << '\n';
}