취미로 코딩하기

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

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

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

매 i번째 날에 들고 있을 수 있는 최대 마르크 액수는 그 이전에 가지고 있을 수 있는 최대 달러 액수를 당일 환전하거나 그 이전에 환전해 들고 있는 두 경우의 최댓값으로 구할 수 있고, 최대 달러 액수 또한 이와 유사하게 구할 수 있다.

위의 관계를 점화식으로 나타내고, 환전 비율에 신경써 구현해 문제를 해결하자.

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

#include <iostream>
using namespace std;
typedef long double ld;

int N;

ld arr[100][2];
ld dp[100][2]; // [0]: marks, [1]: dollars

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

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

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

	dp[0][0] = 100, dp[0][1] = arr[0][0];
	for (int i = 1; i < N; i++) {
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] * (100 / arr[i][1]));
		dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] * (arr[i][0]) / 100);
	}

	cout << dp[N - 1][0];
}

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

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

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

주어지는 주소에서 문제에서 요구하는 문자열을 파싱해 가장 많이 등장한 문자열을 찾는 문제이다.

글쓴이는 다음과 같은 순서로 주소에서 필요한 부분을 파싱했다.

(1) 주어진 주소의 앞에 "https://"가 앞에 존재한다면 제거, 주소의 맨 뒤에 '/' 추가

(2) 앞에서부터 읽어나가며 '/'을 발견하기 전 '.'을 발견한다면 문자열의 맨 앞부터 해당 '.'까지를 제거

(3) '/'을 발견하면 문자열의 맨 앞부터 '/' 전까지가 파싱하려는 문자열이 된다.

주어지는 문자열을 multiset 자료구조로 관리하면 각 문자열이 몇번씩 등장했는지를 쉽게 알아낼 수 있다. 또한 중복없는 출력을 위해 set 자료구조를 이용해 편하게 구현할 수 있다.

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

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

int N;
multiset<string> st;

int cnt;
set<string> ans;

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

	cin >> N;
	while (N--) {
		string s; cin >> s; s += '/';
		if (s.length() > 6 && s.substr(0, 7) == "http://") s.erase(s.begin(), s.begin() + 7);

		while (1) {
			int idx = 0;
			while (s[idx] != '.' && s[idx] != '/') idx++;
			if (s[idx] == '.') s.erase(s.begin(), s.begin() + idx + 1);
			else {
				st.insert(s.substr(0, idx));
				break;
			}
		}
	}

	for (auto& x : st) {
		if (st.count(x) > cnt) {
			cnt = st.count(x);
			ans.clear();
			ans.insert(x);
		}
		else if (st.count(x) == cnt) ans.insert(x);
	}

	cout << cnt << '\n';
	for (auto& x : ans) cout << x << ' ';
}

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

이번에 볼 문제는 백준 2082번 문제인 시계이다.
문제는 아래 링크를 확인하자.

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

시계가 표기하는 문자 X가 의미할 수 있는 가장 작은 숫자 i는 "i를 정상적으로 나타낼 때 켜져있을 수 없는(i를 정상적으로 나타낼 때 꺼져있어야 하는) 다이오드가 X에 켜져있지 않은, 가장 작은 i"와 같다. 이와 같은 관찰을 이용해 각 문자가 나타낼 수 있는 가장 작은 숫자를 찾아 문제를 해결하자.

위와 같이 찾은 숫자들이 올바른 시각을 구성하지 못한다면 주어진 입력은 올바른 시각을 표기할 수 없다는 것을 의미함을 관찰하자. (위에서 구한 수가 가능한 가장 작은 수이기 때문이다.) 따라서 위와 같은 풀이로 문제의 답을 항상 구해낼 수 있음을 보장할 수 있다.

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

#include <iostream>
using namespace std;

string num[10][5] =
{
	{
		"###",
		"#.#",
		"#.#",
		"#.#",
		"###"
	},
	{
		"..#",
		"..#",
		"..#",
		"..#",
		"..#"
	},
	{
		"###",
		"..#",
		"###",
		"#..",
		"###"
	},
	{
		"###",
		"..#",
		"###",
		"..#",
		"###"
	},
	{
		"#.#",
		"#.#",
		"###",
		"..#",
		"..#"
	},
	{
		"###",
		"#..",
		"###",
		"..#",
		"###"
	},
	{
		"###",
		"#..",
		"###",
		"#.#",
		"###"
	},
	{
		"###",
		"..#",
		"..#",
		"..#",
		"..#"
	},
	{
		"###",
		"#.#",
		"###",
		"#.#",
		"###"
	},
	{
		"###",
		"#.#",
		"###",
		"..#",
		"###"
	}
};

string digit[4][5];
int ans[4];

bool func(int i, int dgt) {
	for (int r = 0; r < 5; r++) {
		for (int c = 0; c < 3; c++) {
			if (num[dgt][r][c] == '.' && digit[i][r][c] == '#') return 0;
		}
	}
	return 1;
}

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

	for (int r = 0; r < 5; r++) {
		for (int i = 0; i < 4; i++) cin >> digit[i][r];
	}

	for (int i = 0; i < 4; i++) {
		int dgt = 0;
		while (!func(i, dgt)) dgt++;

		ans[i] = dgt;
	}

	cout << ans[0] << ans[1] << ':' << ans[2] << ans[3];
}

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

이번에 볼 문제는 백준 3182번 문제인 한동이는 공부가 하기 싫어!이다.
문제는 아래 링크를 확인하자.

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

각 선배에 대하여 해당 선배부터 질문을 시작할 때 만나게 되는 선배의 수는 $N$ 이하임을 알 수 있다. 전체 선배의 수가 1000명이므로, 모든 각 선배에 대하여 질문을 시작해보더라도 선배에게 질문을 하는 횟수는 $N^2$ 이하임을 알 수 있다.

따라서 모든 선배에 대하여 그 선배부터 질문을 시작할 때 총 몇 명의 선배를 만나게 되는지를 구하는 시뮬레이션을 각각 돌려 문제를 해결하는 방법은 문제를 해결하기에 충분한 시간복잡도를 가진다. 이와 같은 방법으로 문제를 해결하자.

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

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

int N;
int arr[1001];
int visited[1001];

int ans, mx;

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

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

	for (int i = 1; i <= N; i++) {
		memset(visited, 0, sizeof(visited));
		int cnt = 0, idx = i;
		while (!visited[idx]) {
			visited[idx] = 1;
			idx = arr[idx];
			cnt++;
		}
		if (mx < cnt) mx = cnt, ans = i;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 3181번 문제인 줄임말 만들기이다.
문제는 아래 링크를 확인하자.

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

주어져있는 "쓸모없는 단어"를 제외한 단어들의 첫 문자들을 대문자로 이어 출력하는 문제이다. 단, 첫 단어의 첫 문자는 항상 (대문자로) 출력해주어야 한다.

각 단어가 "쓸모없는 단어"인지를 판단하는 것은 set 자료구조를 이용해 아래와 같이 간단히 구현할 수 있다.

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

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

string s;
set<string> st = { "a", "ali", "i" , "ili", "nego", "ni", "niti", "no", "pa", "te" };

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

	cin >> s; cout << (char)toupper(s[0]);
	while (cin >> s) {
		if (st.find(s) == st.end()) cout << (char)toupper(s[0]);
	}
}

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

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

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

'#'으로 구분되어 있는 각 영역마다 해당 영역의 양과 늑대의 마릿수를 셀 수 있다면 문제를 해결할 수 있을 것이다. 이는 BFS 등의 그래프 탐색 알고리즘을 이용하여 해낼 수 있다.

양과 늑대가 있을 수 없는 '.' 위치를 경계를 포함하여 양과 늑대가 없는 영역으로 생각하더라도 이러한 영역들은 문제의 답에 영향을 주지 않으므로 영역의 구분을 신경쓰면서 구현할 필요는 없다.

만약 '.'을 찾을 때마다 새로운 영역을 찾은 것으로 생각해 영역을 탐색하는 코드를 작성한다면 틀렸습니다를 받을 것이다. 모든 칸에 양 또는 늑대가 들어있는 영역이 존재할 수 있고 그러한 영역에는 '.'이 포함되어 있지 않기 때문이다.

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

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

int R, C;
string board[250];
int ocnt, vcnt;

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void bfs(int qr, int qc) {
	int O = 0, V = 0;
	if (board[qr][qc] == 'o') O++;
	else if (board[qr][qc] == 'v') V++;
	board[qr][qc] = '#';
	
	queue<pair<int, int>> que;
	que.push(make_pair(qr, qc));
	
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc] == '#') continue;
			if (board[rr][cc] == 'o') O++;
			else if (board[rr][cc] == 'v') V++;
			board[rr][cc] = '#';
			que.push(make_pair(rr, cc));
		}
	}

	if (O > V) ocnt += O;
	else vcnt += V;
}

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> board[r];

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] != '#') {
				bfs(r, c);
			}
		}
	}

	cout << ocnt << ' ' << vcnt;
}