취미로 코딩하기

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

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

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

먼저 \(N\)개의 언어의 이름과 각 언어에서 사용되는 몇몇 단어들이 주어진다. 이후로 주어지는 각 문장에 대하여 사용된 단어들을 이용해 각 문장이 어떤 언어인지 추측하는 문제이다.

먼저 N개의 언어별로 주어지는 모든 단어들은 중복이 없다는 점을 이용해 각 단어와 그 단어에 대응되는 언어이름을 대응시키는 map을 구성하면 구현을 간단하게 할 수 있다.

대응되는 단어를 찾을 때마다 언어명을 출력하는 것이 아닌 문장단위로 언어명을 출력해야 한다는 점에 유의해 구현하자.

두 단어가 같은지 판단할 때 대소문자를 구분하지 않아야 한다는 문제의 조건에 유의하자. 또한, '와 -는 단어의 일부로 취급하지만 나머지 라틴알파벳이 아닌 문자는 구분자로 기능한다는 문제의 조건에도 유의하자.

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

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

int N, slen; string sname, s;
map<string, string> mp;

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

	cin >> N;
	while (N--) {
		cin >> sname;
		getline(cin, s); s += ' ';
		slen = s.length();
		int L = 1, R = 1;
		while (L < slen) {
			while (s[R] != ' ') {
				s[R] = tolower(s[R]);
				R++;
			}
			mp.insert(make_pair(s.substr(L, R - L), sname));
			R++;
			L = R;
		}
	}

	getline(cin, s);
	while (getline(cin, s)) {
		s += ' ';
		slen = s.length();

		int L = 0, R = 0;
		while (L < slen) {
			while (('A' <= s[R] && s[R] <= 'Z') || ('a' <= s[R] && s[R] <= 'z') || s[R] == '\'' || s[R] == '-') {
				s[R] = tolower(s[R]);
				R++;
			}
			string tmp = s.substr(L, R - L);
			if (mp.count(tmp)) {
				cout << mp[tmp] << '\n';
				break;
			}
			R++;
			L = R;
		}
	}
}

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

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

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

\(A_k=a_1^2+\cdots +a_k^2\), \(B_k=a_{k+1}+\cdots +a_n\)라 하자. 이 때 문제에서 구하고자 하는 값은 \(1\) 이상 \(n\) 미만의 정수 \(k\)에 대하여 계산한 \(A_k B_k\)의 값들 중 최댓값이 된다. 따라서 \(A_k\)와 \(B_k\)의 값을 미리 빠르게 계산해둘 수 있다면 위 값들을 직접 계산해 답을 구할 수 있다.

한편, \(A_k\)는 \(A_{k-1}+a_k^2\)임을 이용하면 모든 \(A_k\)의 값을 \(O(n)\)으로 구할 수 있고, 이와 비슷하게 방향을 바꿔 계산하는 것으로 모든 \(B_k\)의 값을 \(O(n)\)으로 구할 수 있다. 이는 문제를 해결하기에 충분히 빠른 시간복잡도이다.

위의 관찰을 이용해 문제를 해결하자.

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

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

int N, total; ll totals, mx;
int A[1000000];

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		total += A[i];
	}

	for (int i = 0; i < N; i++) {
		total -= A[i];
		totals += A[i] * A[i];
		mx = max(mx, totals * total);
	}
	cout << mx;
}

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

이번에 볼 문제는 백준 31589번 문제인 포도주 시음이다.
문제는 아래 링크를 확인하자.

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

편의상 모든 포도주의 맛이 다르다고 가정하자.

\(K\)개의 포도주를 순서대로 마실 때, 어떤 연속한 세 포도주의 맛이 내림차순이거나 오름차순이라면 중간 차례로 마신 포도주를 마시지 않더라도 느끼는 총 맛의 차이가 변하지 않음을 관찰하자. 따라서 구하는 값은 처음을 제외하고 이전에 마신 포도주보다 맛없는 포도주를 마시는 것과 맛있는 포도주를 마시는 것을 반복하는 경우에서 찾아볼 수 있다. 0번째로 맛이 0인 포도주를 마셨다고 생각하면 이를 모든 포도주에 적용해 생각할 수 있음을 관찰하자.

이 때, 모든 \(K\)개의 포도주는 이전보다 맛있게 소비한 포도주거나 맛없게 소비한 포도주 둘로 나눌 수 있는데, (마지막으로 소비한 포도주가 이전보다 맛없는 포도주인 경우 그 포도주를 제외하면) \(K\)개의 포도주를 마시며 느낀 맛의 합은 (맛있게 소비한 포도주 맛 총합) - (맛없게 소비한 포도주 맛 총합)으로 계산할 수 있다. 이 값의 최댓값은 가장 맛있는 포도주들을 최대한 (맛있게 소비한 포도주 맛 총합)에 포함되게끔, 그리고 가장 맛없는 포도주들을 최대한 (맛없게 소비한 포도주 맛 총합)에 포함되게끔 포도주를 분류할 때 찾을 수 있음을 관찰할 수 있다.

위 관찰은 맛있는 정도가 같은 포도주가 있는 경우까지 어렵지 않게 확장할 수 있다. 위 내용을 구현해 문제를 해결하자.

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

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

int N, K;
int A[300001];
int L, R;
ll ans;

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

	cin >> N >> K; K++;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A, A + N + 1);

	L = 0, R = N;
	while (K > 1) {
		ans += A[R] - A[L];
		L++, R--, K -= 2;
	}

	cout << ans;
}

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

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

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

주어지는 문자열에서 "long"이 연속으로 반복하는 형태를 제외하면 원래의 문자열에서 변할 수 있는 부분은 없다. 따라서 각 연속한 "long"이 원래의 문자열에서 나타날 수 있는 경우의 수를 각각 구해 곱하는 것으로 문제를 해결할 수 있다.

"long"이 \(k>1\)개 연속한 문자열의 변화 전 문자열은 그대로 "longlong"이었거나 "int"였을 두 가지 경우로 나누어 생각할 수 있다. 각 경우의 문자열의 개수는 각각 "long"이 \(k-2\)개, \(k-1\)개 연속한 문자열의 변화 전 문자열의 수와 같으므로 이를 이용해 "long"이 \(k\)개 연속한 문자열의 변화 전 문자열의 개수를 구할 수 있다. 이는 피보나치 수열의 점화식과 같음을 확인하자.

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

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

int N;
string s;
vector<int> vec;
int old = -1000000007, combo;
ll dp[21];
ll ans = 1;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	dp[0] = dp[1] = 1;
	for (int i = 2; i < 21; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	cin >> N >> s;
	for (int i = 0; i + 3 < N; i++) {
		if (s.substr(i, 4) == "long") vec.emplace_back(i);
	}

	for (auto &x : vec) {
		if (x == old + 4) combo++;
		else {
			ans *= dp[combo];
			combo = 1;
		}
		old = x;
	}
	ans *= dp[combo];

	cout << ans;
}

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

이번에 볼 문제는 백준 29704번 문제인 벼락치기이다.
문제는 아래 링크를 확인하자.

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

잘 알려진 유형 중 하나인 knapsack dp 문제이다.

앞의 \(i\)가지 과제만을 고려하여 과제를 \(t\)일까지 했을 때 내지 않아도 되게 되는 벌금의 최댓값을 \(dp[i][t]\)와 같이 나타내자. \(i+1\)번째 과제를 해결하는 데에 드는 시간이 \(d\), 벌금을 \(w\)라 할 때 \(dp\)는 대략적으로 아래와 같은 식을 만족한다:

\(dp[i+1][t]=\text{max}(dp[i][t], dp[i][t-d]+w)\)

여기서 \(dp[i][t]\)는 \(i+1\)번째 과제를 수행하지 않는 경우를, \(dp[i][t-d]+w\)는 \(i+1\)번째 과제를 수행하는 경우의 내지 않아도 될 벌금의 최댓값을 뜻한다.

대략적이라고 언급한 이유는 인덱스가 벗어나는 경우나 초기상태 등을 위에 제대로 언급해두지 않았기 때문이다. 이 부분은 특별할 것이 없으므로(아무 과제도 안 했을 때 dp의 값은 0일 것이다.) 설명을 생략하겠다. 단, 인덱스 등은 구현할 때 범위를 벗어나지 않게끔 신경 써 구현하자.

문제의 답은 내지 않아도 될 벌금의 최댓값이 아닌 내야 할 벌금의 최솟값임에 유의하자.

아래의 구현은 \(i\)의 값이 증가하면 두 단계 전의 \(i\)값에 대한 \(dp\)의 값을 다시 살펴볼 일이 없다는 점을 이용한 최적화가 포함되어 있다.

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

#include <iostream>
using namespace std;

int N, T, total;
int dp[1001];
int mx;

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

	cin >> N >> T;
	while (N--) {
		int d, w; cin >> d >> w;
		total += w;
		for (int t = T; t >= d; t--) dp[t] = max(dp[t], dp[t - d] + w);
	}

	for (int i = 0; i <= T; i++) mx = max(mx, dp[i]);
	cout << total - mx;
}

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

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

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

먼저 \(i\)마리의 소가 수업을 들을 때 걷을 수 있는 수업료의 최댓값이 얼마일지 생각해보자. 이 값은 가능한 많은 수업료를 낼 수 있는 \(i\)마리의 소를 골라 그 중 가장 작은 값으로 수업료를 책정해 계산할 수 있을 것이다. 이렇게 소를 고르지 않았다면 위에 해당하지 않는 소를 해당하는 소로 바꿔 수업료를 증가하거나 유지하는 것이 항상 가능하므로 이는 항상 올바른 방법임을 알 수 있다.

수업은 소 0마리, 1마리, ..., \(N\)마리가 듣는 경우로 나눌 수 있으므로 각 \(i\)에 대하여 위의 문제의 답을 구해 그 중 가장 큰 경우를 찾아 문제를 해결하자. 

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

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

int N;
ll A[100000];
ll ans, anstuit;

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A, A + N, greater());

	for (int i = 0; i < N; i++) {
		ll val = A[i] * (i + 1);
		if (val >= ans) ans = val, anstuit = A[i];
	}

	cout << ans << ' ' << anstuit;
}