취미로 코딩하기

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

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

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

가장 멀리 꽂아야하는 책 또한 결국 그 위치에 책을 꽂으러 이동해야 하므로, 그 곳으로 책을 꽂으러 갈 때 그 방향으로 꽂아야하는 가장 멀리 있는 책 (최대) K개를 가져갔다가 0으로 돌아오는 그리디 전략으로 책을 채워 문제를 해결하자.

위와 같은 왕복이동의 순서는 바꿔도 무방하므로, 위 과정에서 필요한 가장 먼 왕복거리를 마지막 편도이동으로 잡자.

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

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

int N, K;
vector<int> vec1, vec2;
int ans, mx;

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

	cin >> N >> K;
	while (N--) {
		int x; cin >> x;
		if (x > 0) vec1.emplace_back(x);
		else vec2.emplace_back(-x);
	}

	sort(vec1.begin(), vec1.end());
	sort(vec2.begin(), vec2.end());

	ans = vec1.back() * 2 + vec2.back() * 2;
	mx = max(vec1.back(), vec2.back());
	
	while (vec1.size() > K) {
		for (int k = 0; k < K; k++) vec1.pop_back();
		ans += vec1.back() * 2;
	}
	while (vec2.size() > K) {
		for (int k = 0; k < K; k++) vec2.pop_back();
		ans += vec2.back() * 2;
	}

	ans -= mx;

	cout << ans;
}

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

이번에 볼 문제는 백준 26940번 문제인 나뭇잎 학회이다.
문제는 아래 링크를 확인하자.

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

주어진 기간 중 초콜릿을 새로 구입한 횟수의 최솟값을 구하는 문제이다. 이는 주여진 수열의 인접한 두 수를 순서대로 \(a\),\(b\)라 할 때 \(a<b\)를 만족하는 \((a,b)\)쌍을 세는 것으로 문제를 해결할 수 있다.

반복문을 이용해 위의 값을 구해주자.

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

#include <iostream>
using namespace std;

int N;
int old, ans;

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

	cin >> N >> old; N--;
	while (N--) {
		int cur; cin >> cur;
		if (cur > old) ans++;
		old = cur;
	}

	cout << ans;
}