2019-10-24algorithm / BOJ몇 초 읽기 소요 (대략 91 단어)

[C++]BOJ 2875 - 대회 or 인턴

엄청 간단한 문제였는데 방심했다가 틀렸다.

여자 수 / 2
남자 수
여자 수 + 남자 수 - 인턴 수

3개 중에 가장 작은 값이 답이다. 가장 작은 값을 제외하곤 서로의 반례가 되기 때문.

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n, m, k;
    cin >> n >> m >> k;
    cout << min(min(n/2, m), (n+m-k)/3) << endl;
}

2019-10-24algorithm / BOJ2분 읽기 소요 (대략 263 단어)

[C++]BOJ 10610 - 30

어떤 수가 3의 배수인지 확인하는 방법은 각 자릿수를 모두 더한 값이 3의 배수여야 한다. 이는 간단한 방법으로 증명할 수 있다. 10^n자릿수가 9일 때 3을 더하면 10^n의 자리에서 7만큼을 손해 보고 10^n+1의 자리에서 1의 이득을 본다. -7+1(역시나 3의 배수)

결국엔 계속 3의 배수가 되는데 생각해보니 정렬된 거나 안된 거나 같이 위의 조건을 만족한다면 그냥 모듈러 연산으로 해도 된다는 생각이 들었다. 어쨌든 30의 배수가 되려면 위의 조건에서 0이 문자열에 포함되어 있는지 확인해 봐야 한다.

조건을 모두 만족한 후 내림차순 정렬하면 풀린다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool cmp(char a, char b)
{
	return a > b;
}
int main()
{
    string n;
    cin >> n;
    long long s = 0;
    bool z = false;
    for(int i = 0; i < n.size(); i++)
    {
    	s += (n[i] - '0');
		if(!(n[i] - '0'))
        	z = true;
    }
    if(!z || s % 3)
    	cout << -1 << endl;
    else
    {
        sort(n.begin(), n.end(), cmp);
		cout << n << endl;
    }
}

2019-10-24algorithm / BOJ1분 읽기 소요 (대략 164 단어)

[C++]BOJ 2217 - 로프

다음 로프의 길이가 현재 로프의 길이보다 항상 크거나 같다고 가정했을 때, {앞으로 남은 로프의 수 + 1(자기 자신)} * 자신의 길이가 다음 로프에서 같은 연산을 수행했을 때 보다 작다면 다음 로프의 길이 * (앞으로 남은 로프의 수 + 1)가 최대로 견딜 수 있는 하중이 된다.

이를 반복문 돌리면 풀린다. +정렬까지

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int n;
	cin >> n;
	short a[100001];
	for(int i = 0; i < n ; i++)
	{
		cin >> a[i];
	}
	sort(a, a+n);
	int k = 0;
	for(int i = 0; i < n; i++)
	{
		if(k < a[i] * (n - i))
		{
			k = a[i] * (n - i);
		}
	}
	cout << k;
}

2019-10-24algorithm / BOJ몇 초 읽기 소요 (대략 60 단어)

[C++]BOJ 5585 - 거스름돈

동전 내는 문제에서 거스름돈으로 바뀐 문제.

#include <iostream>
using namespace std;
int main()
{
	short a;
	cin >> a;
	a = 1000 - a;
	int b = 0;
	b += a / 500;
	a = a % 500;
	b += a / 100;
	a = a % 100;
	b += a / 50;
	a = a % 50;
	b += a / 10;
	a = a % 10;
	b += a / 5;
	a = a % 5;
	b += a / 1;
	a = a % 1;
	cout << b;
}

2019-10-24algorithm / BOJ1분 읽기 소요 (대략 152 단어)

[C++]BOJ 1931 - 회의실배정

회의가 끝나는 시간이 빠른 회의 순으로 정렬 후 이전 회의의 끝나는 시간과 현재 회의가 시작하는 시간의 조건을 만족시키면 회의 수를 +1 한다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> p;
int main()
{
	int a;
	cin >> a;
	p b[100001];
	for(int i = 0; i < a; i++)
	{
		cin >> b[i].second >> b[i].first;
	}
	sort(b, b+a);
	int c = 1;
	int l = b[0].first;
	for(int i = 1; i < a; i++)
	{
		if(b[i].second >= l)
		{
			l = b[i].first;
			c++;
		}
	}
	cout << c;
}

2019-10-24algorithm / BOJ몇 초 읽기 소요 (대략 65 단어)

[C++]BOJ 11047 - 동전0

동전금액이 큰 단위부터 나눠가면 된다.

#include <iostream>
using namespace std;
int main()
{
	int n, k;
	cin >> n >> k;
	int v[11];
	for(int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	int g = 0;
	int j = n - 1;
	while(1)
	{
		if(k == 0)
		{
			break;
		}
		if(v[j] <= k)
		{
			g += k / v[j];
			k = k % v[j];
		}
		j--;
	}
	cout << g;
}

2019-10-24algorithm / BOJ몇 초 읽기 소요 (대략 71 단어)

[C++]BOJ 11399 - ATM

앞사람의 인출 시간이 적을 때 전체 인출 시간이 적어진다.

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int time[1001];
	int a;
	cin >> a;
	for(int i = 0; i < a; i++)
		cin >> time[i];
	sort(time, time + a);
	long long b = 0;
	for(int i = 0; i < a; i++)
		for(int j = 0; j < i + 1; j++)
			b += time[j];
	cout << b;
}

[C++]BOJ 2875 - 대회 or 인턴

[C++]BOJ 10610 - 30

[C++]BOJ 2217 - 로프

[C++]BOJ 5585 - 거스름돈

[C++]BOJ 1931 - 회의실배정

[C++]BOJ 11047 - 동전0

[C++]BOJ 11399 - ATM

Links

Categories

Recent

Archives

Tags