[백준] 2주차(9/24~9/30)

#2839 설탕배달

분류: 수학, 다이나믹 프로그래밍, 그리디 알고리즘

#include <iostream>
using namespace std;

int main() {
	int n, count = -1;
	cin >> n;
	
	if (n % 5 == 0) count = n / 5;
	else {
		int quot = n / 5;
		while (quot >= 0) {
			if ((n - (quot * 5)) % 3 == 0) {
				count = quot + (n - (quot * 5)) / 3;
				break;
			}
			--quot;
		}
	}
	printf("%d", count);
}

📍 재귀 이용해서 풀어야하나 했는데 그리디 알고리즘으로 간단하게 풀 수 있는 문제였다. 5로 나누어떨어지는 경우를 제외하고는 n-n/5n, n-n/5(n-1), … n의 값이 3으로 나누어 떨어지는지 확인해보면 된다. 아주 greedy하다.

#11047 동전 0

분류: 그리디 알고리즘

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

int main() {
	int n, k, a, count = 0;
	cin >> n >> k;

	vector<int> coin;
	while (n--) {
		cin >> a;
		if (a <= k) coin.push_back(a);
	}

	reverse(coin.begin(), coin.end());
	for (int i : coin) {
		if (k == 0) break;
		count += k / i;
		k %= i;
	}

	printf("%d", count);
}

📍 2839번에 이어 그리디 알고리즘. 동전 문제 특성상 굉장히 간단히 풀 수 있었다. 어려운 동전 문제를 찾아봐야할듯!

algorithm 라이브러리의 sort 관련 함수

sort(v.begin(), v.end())	// 오름차순 정렬, 마지막 인자로 less<>() 넣어도 동일한 결과
sort(v.begin(), v.end(), greater<>())	// 내림차순 정렬
reverse(v.begin(), v.end())

11866 요세푸스 문제 0

분류: 구현, 자료구조, 큐

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

vector<int> josephus(int n, int k) {
	vector<int> people;
	for (int i = 1; i <= n; ++i)
		people.push_back(i);

	vector<int> v;
	int i = k -1;
	while (!people.empty()) {
		if (i >= n)
			while(i >= n) i -= n;
		v.push_back(people[i]);
		people.erase(people.begin() + i);
		i = i + k - 1;
		--n;
	}
	return v;
}

int main() {
	int n, k;
	cin >> n >> k;

	vector<int> result = josephus(n, k);

	for (int i = 0; i < n; ++i) {
		if (i == 0) printf("<%d", result[i]);
		else printf(", %d", result[i]);
	}
	printf(">");
}

📍 벡터로 풀면서 이게 아닌데… 라고 생각했는데 진짜 아니다!! 다 풀고 분류에 큐 적혀있는거 보고 깨달았다.
그래서 queue로 다시 풀어보았다.

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

void josephusQueue(int n, int k) {
	queue<int> q;
	for (int i = 1; i <= n; ++i)
		q.push(i);

	int i = 1;
	printf("<");
	while (!q.empty()) {
		if (i % k == 0) {
			if (i == k) printf("%d", q.front());
			else printf(", %d", q.front());
		}
		else q.push(q.front());
		q.pop();
		++i;
	}
	printf(">");
}

int main() {
	int n, k;
	cin >> n >> k;
	
	josephusQueue(n, k);
}

📍 큐 방식은 큐가 빌 때까지 k번째일 때는 pop해버리고, 아닐땐 push_back해주는 것이다. 벡터로 풀 때 필요했던 쓸모없는 조건문들을 다 제거할 수 있다.

큐로 풀 때는 그냥 함수 내에서 출력하게끔 했다. 굳이 함수 분리할 필요도 없긴 한데 메인에서 출력할 필요도 없길래.