그리디.. 어렵다.. 문제 11개

BOJ 4796

  • 10’

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

#include <iostream>
using namespace std;

int main() {
    int l, p, v; // 1<ㅣ<p < v
    int cnt = 1;
    while (true) {
        cin >> l >> p >> v;
        if (l == 0 && p == 0 && v == 0) break;

        int ans = 0;
        ans += (v / p) * l;
        int tmp = v - (v / p) * p;
        if (tmp < l) ans += tmp;
        else ans += l;

        printf("Case %d: %d\n", cnt++, ans);
    }
}

comment

2 8 20 0 0 0

ans: 6


BOJ 1449

  • 9’09”

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

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

int main() {
    int n, l;
    cin >> n >> l;
    int arr[1000];
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    sort(arr, arr + n);

    int start = arr[0];
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (arr[i] - start < l) continue;
        cnt++; start = arr[i];
    }

    cout << cnt << endl;
}

comment

4 2 4 3 2 1 ans: 2

4 3 1 2 3 4 ans: 2

3 4 1 2 3 ans: 1


BOJ 17509

  • 23’58”

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

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

struct Element {
	int t; int v;
};

bool cmp(Element e1, Element e2) {
	return e1.t < e2.t;
}

int main() {
	Element arr[11];
	for (int i = 0; i < 11; i++)
		cin >> arr[i].t >> arr[i].v;

	sort(arr, arr + 11, cmp);

	int sum = 0; int min = 0;
	for (int i = 0; i < 11; i++) {
		min += arr[i].t;
		sum += min + 20 * arr[i].v;
	}

	cout << sum << endl;
}


BOJ 11047

  • 5’

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

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

int main() {
	int n, k;
	cin >> n >> k;
	int arr[10];
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	int ans = 0;
	for (int i = n - 1; i > -1; i--) {
		if (arr[i] > k) continue;
		ans += k / arr[i];
		k = k % arr[i];
	}
	cout << ans << endl;
}


BOJ 1931

  • 14’48”

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

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

struct Element {
	int s, e;
};

bool cmp(Element e1, Element e2) {
	if (e1.e == e2.e)
		return e1.s < e2.s;
	return e1.e < e2.e;
}

int main() {
	int n;
	cin >> n;
	Element * arr = new Element[n];
	for (int i = 0; i < n; i++)
		cin >> arr[i].s >> arr[i].e;
	sort(arr, arr + n, cmp);

	int ans = 1;
	int tmp = arr[0].e;
	for (int i = 1; i < n; i++) {
		if (tmp > arr[i].s) continue;
		ans++; tmp = arr[i].e;
	}
	cout << ans << endl;
}

comment

11 11 11 11 11 9 11 10 11 11 11 8 11 7 10 10 10 9 10 10 10 6 10

ans: 7

9 8 8 5 8 3 4 2 5 2 7 8 8 1 10 3 3 10 10

ans: 6

BOJ 11000

  • 22’18”

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

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

struct Element {
	int s, e;
};

bool cmp(Element e1, Element e2) {
	if (e1.s == e2.s)
		return e1.e < e2.e;
	return e1.s < e2.s;
}

int main() {
	int n;
	cin >> n;
	Element * arr = new Element[n];
	for (int i = 0; i < n; i++)
		cin >> arr[i].s >> arr[i].e;
	sort(arr, arr + n, cmp);

	priority_queue<int, vector<int>, greater<int>> room;
	room.push(arr[0].e);
	for (int i = 1; i < n; i++) {
		if (room.top() <= arr[i].s) {
			room.pop(); room.push(arr[i].e);
		}
		else {
			room.push(arr[i].e);
		}
	}
	cout << room.size() << endl;
}

comment

priority_queue<int, vector<int>, greater<int>> room;


BOJ 1700

  • 다시풀기

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

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


int main() {
	int n , k; // 1< < 101
	cin >> n >> k;
	int arr[100];
	for (int i = 0; i < k; i++)
		cin >> arr[i];

	int plug[100] = { 0, };
	int cnt = 0;
	for (int i = 0; i < k; i++) {
		bool plugged = false;
		for(int j = 0; j < n; j++) {
			if (!plug[j]) {
				plug[j] = arr[i]; plugged = true; break;
			}
			if (plug[j] == arr[i]) {
				plugged = true; break;
			}
		}
		if (plugged) continue;

		cnt++;
		int plugidx; int pos = -1;
		for (int j = 0; j < n; j++) {
			int tmp = 0;
			for (int h = i + 1; h < k; h++) {
				if (plug[j] == arr[h]) break;
				tmp++;
			}
			if (pos < tmp) {
				plugidx = j;
				pos = tmp;
			}
		}
		plug[plugidx] = arr[i];
	}

	cout << cnt << endl;

}


BOJ 2212

  • 오래걸림

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

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

int main() {
	int n, k;
	cin >> n >> k;
	int* arr = new int[n];
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	sort(arr, arr + n);

	int* diff = new int[n - 1];
	for (int i = 0; i < n - 1; i++) {
		diff[i] = arr[i + 1] - arr[i];
	}
	sort(diff, diff + n - 1);

	int ans = 0;
	for (int i = 0; i < n - k; i++) {
		ans += diff[i];
	}
	cout << ans;
}

comment

해설 보고도 이해가 안 됐던 문제..

예제 입력 1 3 6,6 7 9 에 k 개의 집중국을 세우는 것을 생각해보자.

그렇다면 각각의 거리는 2 3 0 1 2 로 n(=6)개의 센서보다 하나 적은 5개의 거리가 나온다.

집중국의 개수 k 는

  1. n <= k, n 개의 센서보다 크거나 같으면 각 n 개에 하나 이상을 세우므로 정답은 0 이다.

  2. k < n, n 개의 센서보다 적은 수를 세웠을 때, 수신 가능 영역을 최소로 하려면, 각 집중국이 최대로 거리가 멀어지면 된다.

k = 1, 집중국은 모든 센서를 포함해야 하므로, 2 + 3 + 0 + 1 + 2 이다. 수직선 위에 1부터 9까지의 직선을 그린 셈이다.

k = 2, 수직선에 직선이 두 개로 나누어져야 한다. 하지만 이 두 개로 나누어진 직선을 최대로 멀리 떨어져 있어야 한다. 따라서 가장 먼 거리 3을 제외한 2 + 0 + 1 + 2 이다. 수직선 위에 1부터 3, 6부터 9까지 2개의 직선을 그린 셈이다.

k = 3, 수직선에 최대로 멀리 떨어진 직선이 세 개가 되어야 한다. 가장 먼 거리 순인 3과 2를 제외한 0 + 1 + 2 이다. 1에 하나, 3에 하나, 6부터 9까지 하나이다. 나머지도 같은 방법으로 구할 수 있다.


BOJ 13904

  • 오래걸림

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

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

bool cmp(pair<int, int> p1, pair<int, int> p2) {
	if (p1.second == p2.second) return p1.first > p2.first;
	return p1.second > p2.second;
}

int main() {
	int n; cin >> n;
	pair<int, int>* arr = new pair<int, int>[n];
	int maxday = 0;
	for (int i = 0; i < n; i++) {
		cin >> arr[i].first >> arr[i].second;
		maxday = max(maxday, arr[i].first);
	}
	sort(arr, arr + n, cmp);

	int* ans = new int[maxday + 1]();
	for (int i = 0; i < n; i++) {
		for (int j = arr[i].first; j > 0; j--) {
			if (ans[j] == 0) {
				ans[j] = arr[i].second;
				break;
			}
		}
	}

	int sum = 0;
	for (int k = 1; k <= maxday; k++) {
		sum += ans[k];
	}
	cout << sum;
}

comment

하루를 박스라고 생각하자. 그러면 주어진 n 개의 과제 중 가장 마감일이 늦는(큰) 수가 박스의 개수이다. max(d)개의 박스 안에 최대한 많이 점수를 넣는 경우를 구하면 된다. 이때 점수가 높은 순 대로 넣어야 하고, 박스(하루)의 인덱스(1<= i <= max(d))보다 마감일(1<= j <= max(d))은 같거나 작아야 한다. 즉, 마감일 j 를 넣을 수 있는 곳은 박스의 인덱스가 1 <= i <= j 일때이다.


BOJ 15748

  • 42’45”

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

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

bool cmp(pair<long long, long long> p1, pair<long long, long long> p2) {
	if (p1.second == p2.second) return p1.first > p2.first;
	return p1.second > p2.second;
}

int main() {
	int L, N, rf, rb;
	cin >> L >> N >> rf >> rb;
	pair<long long, long long>* stop = new pair<long long, long long>[N]();
	for (int i = 0; i < N; i++) {
		cin >> stop[i].first >> stop[i].second;
	}
	sort(stop, stop + N, cmp);

	int sec = rf - rb;
	long long last = 0;
	long long ans = 0;
	for (int i = 0; i < N; i++) {
		if (last < stop[i].first)
		{
			ans +=
				(stop[i].first - last)  * (stop[i].second * sec);
			last = stop[i].first;
		}
	}

	cout << ans << endl;
}

comment

Bessie 는 B, Farmer 는 F 로 부르겠다.

B 는 1미터를 갈때마다 rf - rb 초를 쉴 수 있다. 예제에서 보듯이 B 가 1 미터를 3 초에 가고, F 가 4 초에 간다면, B 는 1 미터를 3 초만에 가서 1 초 동안은 F 를 기다릴 수 있다. 그 이상 쉬면 F 가 앞지르기 때문에 쉴 수 없다. 다만, B 가 F 를 앞지르는 것은 가능하기에 먼저 k 미터를 가서 (rf - rb) * k 초 만큼 쉴 수 있다.

그렇다면 점수 c 가 높은 순대로 최대한 오래 쉬는 것이 점수를 최대화 하는 방법일 것이다.

위치 x 에서 쉴 수 있는 시간은 {(현재 위치) - (이전에 쉬었던 위치)} * (rf - rb) 이다. 이전에 쉬었던 위치가 없으면 0 으로 판단한다.

자료형 범위를 잘못 설정한 걸 20분 만에 알았다 ^^;


BOJ 1493

*

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

comment

4 4 8 의 박스에는 4 4 4 가 2개 필요하다. ( 2 = 4/4 * 4/4 * 8/4 = 1 * 1 * 2)

그런데 4 4 4 는 1개 이므로 2 - 1 = 1 개가 더 필요하다.

남은 박스의 크기는 4 4 4 이다.

4 4 4 의 박스에는 2 2 2 가 8개 필요하다. ( 8 = 4/2 * 4/2 * 4/2 = 2 * 2 * 2)

남은 박스의 크기는