2024 - 11- 25 C++ 코딩테스트 10주완성 D+65

백준 14469 문제 - 소가 길을 건너간 이유

 

난이도

 

이웃 농장의 소가 길을 마구잡이로 건너는 것에 진절머리가 난 존은 극단의 결정을 내린다.

 

농장 둘레에 매우 큰 울타리를 짓는 것이다. 이렇게 하면 근처 농장 출신의 소가 들어올 일이 거의 없다.

 

이 일로 주변 소들이 분개하였다. 친구네 집에 놀러 갈 수 없을 뿐만 아니라, 매년 참가하던 국제 젖 짜기 올림피아드에도 올해는 참가할 수 없게 되었기 때문이다.

 

이웃 농장의 소 중 존의 농장에 방문할 수 있는 소가 조금 있긴 하지만, 그들도 안심할 수 있는 건 아니다.

 

존의 농장에 들어가는 문은 하나밖에 없고, 그 문을 통과하려면 감시관의 길고 긴 검문을 받아야 한다.

 

여러 마리의 소가 한 번에 들어가려고 하면 줄이 그 만큼 길어진다.

 

N마리의 소가 이 농장에 방문하러 왔다.

 

소가 도착한 시간과 검문받는 데 걸리는 시간은 소마다 다르다. (물론 같을 수도 있다.)

 

두 소가 동시에 검문을 받을 수는 없다.

 

예를 들어, 한 소가 5초에 도착했고 7초 동안 검문을 받으면, 8초에 도착한 그 다음 소는 12초까지 줄을 서야 검문을 받을 수 있다.

 

모든 소가 농장에 입장하려면 얼마나 걸리는 지 구해보자.

 

입력

 

첫 줄에 100 이하의 양의 정수 N이 주어진다.

다음 N줄에는 한 줄에 하나씩 소의 도착 시각과 검문 시간이 주어진다. 각각 1,000,000 이하의 양의 정수이다.

 

출력

 

모든 소가 농장에 입장하는 데 걸리는 최소 시간을 출력한다.

 

실습코드

 

#include <bits/stdc++.h>

using namespace std;

int n,ret = 0,at,it;
vector<pair<int,int>> v;

int main()
{
    cin >> n;

    for(int i =0; i < n; i++)
    {
        cin >> at >> it;
        v.push_back({at,it});
    }
    
    sort(v.begin(),v.end());

    for(int i =0; i < v.size(); i++)
    {
        if(v[i].first > ret) ret = v[i].first;

        ret += v[i].second;
    }

    if(ret == 0) return 0;

    else cout << ret;
}

 

실버4 문제라 그런지.. 실력이 늘어서 그런지..!! 잘 풀린다 기분이 좋다 ㅎㅎㅎㅎ

 

문제의 로직은 간단하다.

 

먼저 입력받은 각 소마다 도착시간과 검문시간을 Vector<pair<int,int>> v안에 저장해준다음

 

sort를 이용하여 정렬하여준다.

 

v 사이즈만큼 반복문을 돌려 v를 순차적으로 검사해준다.

 

v[i] 의 도착시간이 ret보다 클 경우, 그 시간만큼 기다려야하므로 ret = v[i].first를 하여준다.

 

그리고 검문시간인 v[i].second를 더해준다.

 

이렇게 반복문이 끝나고 ret을 출력시켜주면 완벽하다 ㅎㅎㅎ

 

강의실습코드도 확인해보자!

 

#include<bits/stdc++.h>

using namespace std;
int n;
int main(){
	cin >> n; 
	vector<pair<int,int>> a(n);
	for(int i =0; i < n; i++) cin >> a[i].first >> a[i].second;
	sort(a.begin(),a.end()); 
	int realTime = a[0].first + a[0].second;
	for(int i = 1; i < a.size(); i++){
		realTime = max(realTime, a[i].first);
		realTime += a[i].second;
	}
	cout << realTime << "\n"; 
    return 0;
}

 

차이점이라고 따지자면! 내 코드에서는 조건문으로 realtime 부분을 갱신했는데,

 

여기서는 max 함수를 통하여 realtime을 갱신한다! 그외는 차이점이 없다!

 

다음 문제로 가보자~

 

---

 

백준 1931 문제 - 회의실 배정

 

난이도

 

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.

 

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

 

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

 

회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

 

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.

시작 시간과 끝나는 시간은 2^31 -1 보다 작거나 같은 자연수 또는 0이다.

 

출력

 

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

실습코드

 

#include <bits/stdc++.h>

using namespace std;

vector<pair<int,int>> v;
int n,ret = 0,st,et,t = 0;

int main()
{
    cin >> n;

    for(int i=0; i <n; i++)
    {
        cin >> st >> et;
        v.push_back({st,et});
    }

    sort(v.begin(),v.end());
    while(v.size() > ret)
    {
        int temp_ret = 0;
        t = v[0].second;
        temp_ret++;
        
        for(int j = 1; j < v.size(); j++)
        {
            if(v[j].first >= t)
            {
                t = v[j].second;
                temp_ret++;
            }
        }
        t = 0;
        ret = max(ret,temp_ret);
        v.erase(v.begin());
    }

    cout << ret;
    
}

 

시간복잡도를 생각해보았을 때, 1억이 넘어 절대 안될꺼라고 생각했지만..

 

이미 코드를 다 짜버린 상태였다.. 테스트 케이스는 통과하였지만 역시나 백준에서는..

 

 

"시간 초과"

 

흠.. 강의실습코드를 봐보자!

 

강의실습코드

 

#include <bits/stdc++.h>
using namespace std;
int from, to, n, idx = 0, ret = 1;  
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    vector<pair<int, int>> v; 
    for(int i = 0; i < n; i++){
        cin >> from >> to;
        v.push_back({to, from}); 
    }
    sort(v.begin(), v.end()); 
    from = v[0].second; 
    to = v[0].first;   
    for(int i = 1; i < n; i++){
        if(v[i].second < to) continue; 
        from = v[i].second; to = v[i].first;ret++; 
    } 
    cout << ret << '\n';
    return 0;
}

 

어떻게 보면 간단한 로직인데, 생각이 나질 않으면 시간이 조금 걸릴 문제이다.

 

여기 로직은 입력받은 from이 아니라 to를 기준으로 정렬을 하여, 탐색하여주는 것이다.

 

이유는 회의가 끝나는 시간을 기준으로 정렬하고, 끝나는 시간보다 큰 시간을 비교하면

 

둘 다 오름차순으로 정렬되기때문에

 

최소 회의시간을 가지는 회의순으로 탐색을 진행할 수 있기 때문이다.

 

처음 from을 입력받은 저장한 다음, 이전 탐색에서 저장한 from보다 현재 탐색의 to가 더 크면,

 

from의 값을 현재 탐색의 to로 갱신시켜주고, ret을 증감시켜준다.

 

이렇게 하여서 나온 ret의 값을 출력시켜주면 최대로 할 수 있는 회의의 개수가 나오게된다!

---

 

백준 1644 문제 - 소수의 연속합

 

난이도

 

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수  없는 자연수들도 있는데, 20이 그 예이다.

 

7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다.

 

또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

 

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

 

출력

 

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

 

실습코드

 

#include <bits/stdc++.h>
using namespace std;  
bool che[4000001];
int n, a[2000001], p, lo, hi, ret, sum; 
 
int main(){
	scanf("%d", &n); 
    for(int i=2; i<=n; i++){
		if(che[i]) continue;
		for(int j=2*i; j<=n; j+=i){
			che[j] = 1;
		}
	}
	for(int i=2; i<=n; i++){
		if(!che[i]) a[p++] = i;
	}  
    while(1){
        if(sum >= n) sum -= a[lo++];
        else if(hi == p)break;
        else sum += a[hi++];
        if(sum == n) ret++;
    } 
    printf("%d\n", ret); 
}

 

처음엔 소수를 구하는 코드자체를 어떻게 짜야될지 몰랐다!

 

하지만 이 코드를 보니 이중반복문을 통해서 2부터 N까지 반복문이 있으면 해당 i의 값을 j에 n까지 더해주고 해당 배열의

 

값을 1로 대입시켜줌으로서, 소수가 아닌 배열은 모두 1로 값을 대입받게 된다!

 

그리고 배열의 값이 0인 인덱스는 해당 탐색의 i값으로 대입시켜준다.

 

이 배열과 투 포인터를 이용하여

 

소수를 더한 합이 n보다 클 경우 왼쪽 포인터인 lo를 빼준다음 한칸 오른쪽으로 옮기고,

 

소수를 더한 한이 n보다 작을 경우 오른쪽 포인터인 hi를 더한다음 오른쪽으로 한칸 옮겨준다.

 

이렇게 하여서 sum이 n값이랑 동일한 경우일떄 ret을 증감시켜주면 경우의 수를 찾을 수 있다!