취미로 코딩하기

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

이번에 볼 문제는 백준 6844번 문제인 Keep on Truckin'이다.
문제는 아래 링크를 확인하자.

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

각 모텔에 도달할 수 있는 경우의 수는 해당 모텔에서 음의 방향으로 폐구간 [A,B]에 속한 수만큼 떨어진 각 모텔들까지 도달할 수 있는 경우의 수의 합과 같음을 관찰하자.

위의 관찰을 이용하면 문제를 해결하는 DP 알고리즘을 간단히 고안해낼 수 있다. 이를 구현해주자.

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

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

int A, B, N;
int motel[14001];
ll dp[14001];

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

	dp[0] = 1;
	motel[0] = motel[990] = motel[1010] = motel[1970] = motel[2030] = motel[2940] = motel[3060] = motel[3930] = motel[4060] = motel[4970] = motel[5030] = motel[5990] = motel[6010] = motel[7000] = 1;

	cin >> A >> B >> N;
	while (N--) {
		int x; cin >> x;
		motel[x] = 1;
	}

	for (int i = 0; i < 7000; i++) {
		if (!motel[i]) continue;
		for (int k = A; k <= B; k++) {
			dp[i + k] += dp[i];
		}
	}

	cout << dp[7000];
}

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

이번에 볼 문제는 백준 6842번 문제인 Deal or No Deal Calculator이다.
문제는 아래 링크를 확인하자.

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

문제의 요구에 따라 (남은 briefcase에 든 돈의 총합) / (남은 briefcase의 개수) 과 (deal로 제안된 값)의 대소 비교에 따라 "deal" 또는 "no deal"을 출력하는 프로그램을 작성하자.

부동 소수점 오차가 걱정되는 경우, 남은 briefcase의 개수는 항상 양의 정수이므로 위 대소 비교 결과는 (남은 briefcase에 든 돈의 총합)과 (deal로 제안된 값) * (남은 briefcase의 개수)의 대소 비교 결과와 같음을 이용하는 것으로 실수 연산을 피할 수 있다.

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

#include <iostream>
using namespace std;

int N, cnt, total = 1691600, deal;
int val[11] = { 0,100,500,1000,5000,10000,25000,50000,100000,500000,1000000 };

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

	cin >> N; cnt = 10 - N;
	while (N--) {
		int x; cin >> x;
		total -= val[x];
	}

	cin >> deal;
	if (deal * cnt > total) cout << "deal";
	else cout << "no deal";
}

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

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

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

모든 대문자 c에 대하여 (첫 phrase에 있는 c의 개수) - (두번째 phrase에 있는 c의 개수)가 0이라면 두 문자열은 anagram이고 그렇지 않으면 anagram이 아니라는 성질을 관찰하자.

위의 관찰을 이용해 위의 값을 저장할 배열을 하나 만들어 반복문을 이용해 문제를 해결하자.

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

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

string s;
int cnt[128];

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

	getline(cin, s);
	for (auto& l : s) cnt[l]++;
	getline(cin, s);
	for (auto& l : s) cnt[l]--;

	for (char c = 'A'; c <= 'Z'; c++) {
		if (cnt[c]) {
			cout << "Is not an anagram.";
			return 0;
		}
	}

	cout << "Is an anagram.";
}

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

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

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

입력으로 주어지는 각 문자열에 대하여 문제에 주어진 변역표에 존재한다면 번역된 문자열을, 그렇지 않다면 원형 그대로의 문자열을 출력해 문제를 해결하자. 이는 map을 이용해 간편하게 구현할 수 있다. map을 사용하지 않더라도 조건문을 이용해 구현할 수도 있다.

'와 ’는 다른 문자임에 유의하자. (예제 출력 참고)

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

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

map<string, string> mp;
string s;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	mp.insert(make_pair("CU", "see you"));
	mp.insert(make_pair(":-)", "I’m happy"));
	mp.insert(make_pair(":-(", "I’m unhappy"));
	mp.insert(make_pair(";-)", "wink"));
	mp.insert(make_pair(":-P", "stick out my tongue"));
	mp.insert(make_pair("(~.~)", "sleepy"));
	mp.insert(make_pair("TA", "totally awesome"));
	mp.insert(make_pair("CCC", "Canadian Computing Competition"));
	mp.insert(make_pair("CUZ", "because"));
	mp.insert(make_pair("TY", "thank-you"));
	mp.insert(make_pair("YW", "you’re welcome"));
	mp.insert(make_pair("TTYL", "talk to you later"));
	
	while (getline(cin, s)) {
		if (mp.count(s)) cout << mp[s] << '\n';
		else cout << s << '\n';
	}
}

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

이번에 볼 문제는 백준 6840번 문제인 Who is in the middle?이다.
문제는 아래 링크를 확인하자.

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

주어지는 세 수중 중간크기의 값을 찾아 출력하는 문제이다.

세 수를 배열에 담아두고 std::sort를 이용해 이 수들을 크기순으로 정렬하는 것으로 문제를 간단히 해결할 수 있다.

굳이 정렬을 사용하지 않더라도, 어떤 수가 다른 두 수보다 동시에 크지도, 동시에 작지도 않다는 것을 조건문으로 확인해 조건문만으로도 문제를 해결할 수도 있을 것이다.

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

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

int arr[3];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	for (int i = 0; i < 3; i++) cin >> arr[i];

	sort(arr, arr + 3);

	cout << arr[1];
}