[알고리즘 연습] 2021년도 11월 첫째주 학습 (D번 문제 풀이)

AtCoder Beginner Contest 227 (D번 문제): 이분탐색
Codeforces Round #753 (Div.3) (D번 문제): 그리디

 

대회를 진행할 때 D번 문제에서 대부분 막혀서, 풀지 못한 D번 문제들을 기록해두고자 한다.

 

1. AtCoder Beginner Contest 227 (D번 문제)

문제

https://atcoder.jp/contests/abc227/tasks/abc227_d

N 개의 부서에 Ai명의 직원들이 있는데, K 개의 다른 부서에서 K 명을 뽑아오려고 한다. 이렇게 뽑았을 때 만들 수 있는 project의 최대 개수를 구해야한다.

입력
3 3
2 3 4
정답
2

풀이

https://atcoder.jp/contests/abc227/editorial/2919

이분 탐색

 

코드

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, k; cin >> n >> k;
    vector<long long> v(n);
    for(long long &x : v) cin >> x;
    long long ok = 0, ng = 1e18 / k;
    while(ng - ok > 1){
        long long md = (ok + ng) / 2, sum = 0;
        for(long long x : v) sum += min(x, md);
        if(sum >= k * md) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}

 

2. Codeforces Round #753 (D번 문제)

문제

https://codeforces.com/contest/1607/problem/D

숫자들마다 파란색인지 빨간색인지를 정해주고, 매번 아래의 동작 중 하나를 선택한다.

• either you can select any blue element and decrease its value by 1 (파란 숫자 1 빼기)
• or you can select any red element and increase its value by 1 (빨간 숫자 1 더하기)

숫자들을 1부터 n 까지의 순열로 만들 수 있는지 가능 여부를 출력한다.

입력
8
4
1 2 5 2
BRBR
2
1 1
BB
5
3 1 4 2 5
RBRRB
5
3 1 3 1 3
RBRRB
5
5 1 5 1 5
RBRRB
4
2 2 2 2
BRBR
2
1 -2
BR
4
-2 -1 4 0
RRRR

출력
YES
NO
YES
YES
NO
YES
YES
YES

 

풀이 & 코드

https://codeforces.com/contest/1607/submission/134073147

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector <int> v;
int a[1000005];
signed main(int argc, char** argv) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		int n;
		cin >> n;
		for(int i=1;i<=n;i++)
			cin >> a[i];
		string s;
		v.clear();
		cin >> s;
		s=' '+s;
		for(int i=1;i<=n;i++)
		{
			if(s[i]=='B') v.push_back(a[i]);
		}
		sort(v.begin(),v.end());
		int flag=1;
		for(int i=0;i<v.size();i++)
			if(v[i]<=i) flag=0;
		v.clear();
		for(int i=1;i<=n;i++)
		{
			if(s[i]=='R') v.push_back(a[i]);
		}
		sort(v.begin(),v.end());
		int now=n;
		for(int i=(int)v.size()-1;i>=0;i--)
		{
			if(v[i]>now) flag=0;
			--now;
		}
		if(flag)
		{
			cout << "YES\n";
		}
		else cout << "NO\n";
	}
	return 0;
}

https://codeforces.com/contest/1607/submission/134082713

void solve() {
	int n; cin >> n;
	vector <int> v(n); cin >> v;
	vector <int> r, b;
	for (int i = 0; i < n; i++) {
		char c; cin >> c;
		if (c == 'R') r.push_back(v[i]);
		else b.push_back(v[i]);
	}
	sort(rall(r));
	sort(all(b));
 
	for (int i = 0; i < r.size(); i++) {
		if (r[i] > n - i) {
			cout << "NO";
			return;
		}
	}
	for (int i = 0; i < b.size(); i++) {
		if (b[i] < i + 1) {
			cout << "NO";
			return;
		}
	}
 
	cout << "YES";
}

이 방법이 반례가 없는 풀이 방법이 맞는 것일까?