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

[C++]BOJ 1946 - 신입 사원

문제에 헷갈리는 문장이 있었다.

“다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다.”

???????????

한참을 보다가 다음 줄 보고 이해했다.

“즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.”

ㅇㅎ

이전에 회의실 배정인가 거기서 썼던 pair를 쓰면 편하겠단 생각이 들었다.

first는 어차피 오름차순으로 정렬되니 다음 사람의 점수보다 무조건 낮을 것이고 그 와중에 second까지 작으면 조건에 의해 걔는 탈락이다.

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

[C++]BOJ 1541 - 잃어버린 괄호

가장 작은 답이 나오려면 +끼리 괄호로 묶고 계산하면 된다. 라고 생각했지만 계속 반례가 생각나서 이건 아닐 거라고 판단했고 그냥 첫 번째 -가 나온 순간부터 다 빼버리면 처음 생각했던 것보다 단순하게 끝난다.

+아스키코드 10은 line feed (다음 줄)

#include <iostream>
using namespace std;
int main()
{
	bool ch = false;
	int a, b;
	char c;
	scanf("%d", &a);
	for(;scanf("%c", &c), c != 10;)
	{
		if(c == '-') ch = true;
		scanf("%d", &b);
		if(ch) a -= b;
		else a += b;
	}
	cout << a;
}

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

[C++]BOJ 1120 - 문자열

단순 그리디. B 안에서의 차이가 가장 적은 A를 구하면 그게 답이다.

추가하는 연산은 무조건 차이가 가장 적게 할 테니까 신경 쓰지 않는다.

#include <iostream>
using namespace std;
int main()
{
	char a[50], b[50];
	cin >> a >> b;
	int al = sprintf(a, "%s", a);
	int bl = sprintf(b, "%s", b);
	int c = 51;
	for(int i = 0; i < bl - al + 1; i++)
	{
		int co = 0;
		for(int j = 0; j < al; j++)
		{
			if(b[j+i] != a[j]) co++;
		}
		if(co < c) c = co;
	}
	cout << c;
}

지금보면 좀 한심한 코드다.

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 1946 - 신입 사원

[C++]BOJ 1541 - 잃어버린 괄호

[C++]BOJ 1120 - 문자열

[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