Posted 2021-05-13Updated 2021-05-134 minutes read (About 534 words)

B1931

개요

백준 문제 1931번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 150분
https://www.acmicpc.net/problem/1931

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

코드


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

int N;
vector<pair<int,int>> v;
vector<pair<int,int>> startV;

void wrongSolve()
{
	cin >> N;
	int buf1,buf2,count = 1;
	for(int i=0;i<N;i++)
	{
		cin >> buf1 >> buf2;
		startV.push_back({buf1,buf2});
	}		
	sort(startV.begin(),startV.end());

	int selConfStart = startV[0].first;
	int selConfEnd = startV[0].second;
	//cout << "시작 : " << selConfStart << " " << selConfEnd << endl;

	for (int i = 1; i < startV.size(); ++i)
	{
		//지금 제일 작은 애
		//하이재킹
		if(selConfEnd > startV[i].second)
		{
			selConfStart = startV[i].first;
			selConfEnd = startV[i].second;
			//cout << selConfStart << " " << selConfEnd << endl;
		}
		//종료
		else if(selConfEnd <= startV[i].first)
		{
			selConfStart = startV[i].first	;
			selConfEnd = startV[i].second;
			count++;
			//cout << selConfStart << " " << selConfEnd << endl;
		}
	}
	cout << count;



}

bool sortbysec(const pair<int,int> &a,const pair<int,int> &b)
{
	return (a.second < b.second);
}

void rightSolve()
{
	cin >> N;
	int buf1,buf2;
	int count = 0;
	for(int i=0;i<N;i++)
	{
		cin >> buf1 >> buf2; 
		v.push_back(make_pair(buf1,buf2));
	}
	sort(v.begin(),v.end());
	sort(v.begin(),v.end(),sortbysec);
	int min = v[0].second;
	count++;
	for(int i=1;i<N;i++)
	{
		if(v[i].first >= min)
		{
			min = v[i].second;
			count++;
		}
	}

	cout << count;
}



int main()
{
	wrongSolve();

}

풀이

시작 시간으로 정렬
두가지 경우로 나눠서 생각
1 더 나은 (더 빨리 종료하는) 회의가 있으면 하이재킹
2 회의가 종료됐다면 카운트

배울 점, 메모

위 두가지 접근은 처음부터 생각하는데 어려움이 없었다.
그러나 코드 구현상에서 문제의 몇가지 조건에 맞지않는 등이 있어서 실패를 많이 했다
하지만 다음날 다시 천천히 구현하니 꽤 쉽게 풀렸던 문제

Posted 2021-05-11Updated 2021-05-123 minutes read (About 416 words)

B2875

개요

백준 문제 2875번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 90분
https://www.acmicpc.net/problem/2875

문제

백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)

백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다.

백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다.

여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다.

코드

#include <iostream>
using namespace std;

int man,woman,objIntern;
int minTeam = 0;


void greedy()
{
	int intern = 0;
	while(objIntern != intern)
	{
		//여자 한명 빼도 팀 충족
		if((woman-1)/2 >= minTeam)
		{
			woman--;
			intern++;
		}
		//남자 한명 빼도 팀 충족
		else if(man > minTeam)
		{
			man--;
			intern++;
		}
		else if(woman/2 > man)
		{
			//여자뺀다
			woman--;
			intern++;
			minTeam--;
		}
		else
		{
			man--;
			intern++;
			minTeam--;
		}
	}

	cout << minTeam;	
	


}


void solve()
{
	cin >> woman >> man >> objIntern;
	minTeam = min(man,woman/2);
	greedy();

}

int main()
{
	solve();


}

풀이

팀이 충족하는 한 남자나 여자를 빼는 것이 제일 큰 우선순위
팀이 충족하지 않는 경우에는 둘 중에 뺄 사람을 골라야함 -> 최대한 팀이 깨지지 않게 (woman/2 > man)

배울 점, 메모

Posted 2021-05-11Updated 2021-05-122 minutes read (About 299 words)

B10610

개요

백준 문제 10610번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 60분
https://www.acmicpc.net/problem/10610

문제

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

코드

1
2
3

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

풀이

기초 수학을 이용해야 하는 문제
30의 배수이므로 0이 포함돼야하며
각 자리수를 더했을 때 3의 배수라면 30의 배수임

배울 점, 메모

Posted 2021-05-11Updated 2021-05-12a minute read (About 163 words)

B11047

개요

백준 문제 11047번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 20분
https://www.acmicpc.net/problem/11047

문제

동전을 적절히 사용해서 주어진 가치 K를 만들어야함

코드

#include <iostream>

using namespace std;

const int MAX = 10;
int coinVal[MAX];
int N;
int objVal;
void greedy()
{
	int sum = 0;
	int valIdx = N-1;
	int countAddCoin = 0;
	while(objVal != sum)
	{
		if(sum + coinVal[valIdx] > objVal)
		{
			valIdx--;
		}
		else
		{
			sum += coinVal[valIdx];
			countAddCoin++;
		}
	}	
	cout << countAddCoin;
}


void solve()
{
	cin >> N >> objVal; 
	for(int i=0;i<N;i++)
	{
		cin >> coinVal[i];
	}
	greedy();
}	


int main()
{

	solve();
}

풀이

항상 1원짜리가 들어와서 걱정없이 그리디를 적용할 수 있음.
K를 넘지않는 제일 큰 동전을 추가하면 해결

B1931

개요

문제

코드

풀이

배울 점, 메모

B2875

개요

문제

코드

풀이

배울 점, 메모

B10610

개요

문제

코드

풀이

배울 점, 메모

B11047

개요

문제

코드

풀이

배울 점, 메모

Categories

Recents

Archives

Tags

Subscribe for updates