Bin_S+StudyRoom

• 문제

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

• 입력

첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다.

• 출력

하나씩 플러그를 빼는 최소의 횟수를 출력하시오.

• 예제 입력

2 7
2 3 2 3 1 2 7

• 예제 출력

2

• 접근방식

일단 미래의 나타날 숫자를 미리 알고 있으므로 가장 먼 미래(뒤에 있는 인덱스)에 나타나는 수를 찾아서 바꾸고 경우의 수를 1 추가하면 된다.
방문 처리할 visited가 필요하고 전기 용품이 꽂혀있는 벡터가 필요하다.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, k, result, a[104], visited[104];
vector<int> v;

int main()
{
    cin >> n >> k;

    for (int i = 0; i < k; i++)
    {
        cin >> a[i];
    }

    for (int i = 0; i < k; i++)
    {
        if (!visited[a[i]])
        {
            if (v.size() == n)
            {
                int last_idx = 0, pos;
                for (int element : v)
                {
                    int here_pick = 99999999;
                    for (int j = i + 1; j < k; j++) // 가장 먼 미래에 참조 되는 것을 찾음
                    {
                        if (element == a[j])
                        {
                            here_pick = j;
                            break;
                        }
                    }
                    if (last_idx < here_pick)
                    {
                        last_idx = here_pick;
                        pos = element;
                    }
                }
                visited[pos] = 0;
                result++;
                v.erase(find(v.begin(), v.end(), pos));
            }
            v.push_back(a[i]);
            visited[a[i]] = 1;
        }
    }

    cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1700

• 문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

• 출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

• 예제 입력

9
5 12 7 10 9 1 2 3 11
13

• 예제 출력

3

• 접근방식

두 수를 가지고 무엇을 한다고 했을 때 투 포인터로 생각을 했고 정렬을 하고 left와 right를 정해주고 right의 값이 left보다 크면 탐색을 종료하는 반복문을 만들어 두 수의 합이 x와 같으면 경우의 수가 증가하고 right를 감소시키고 두 수의 합이 x보다 크면 right만 감소하여 다시 탐색, 두 수의 합이 x보다 작으면 left만 증가시켜 다시 탐색한다.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m, x, result;
vector<int> v;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> m;
        v.push_back(m);
    }

    sort(v.begin(), v.end());

    int left_p = 0, right_p = n - 1;
    while (left_p < right_p)
    {
        if (v[left_p] + v[right_p] == x)
        {
            right_p--;
            result++;
        }
        else if (v[left_p] + v[right_p] > x)
        {
            right_p--;
        }
        else if (v[left_p] + v[right_p] < x)
        {
            left_p++;
        }
    }
    cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/3273

• 문제

길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.

• 입력

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

두 번째 줄에는 수열을 나타내는 N개의 정수가 주어진다. 수열에 나타나는 수는 모두 1 이상 100,000 이하이다.

• 출력

조건을 만족하는 경우의 수를 출력한다.

• 예제 입력

5
1 2 3 4 5

5
1 2 3 1 2

5
1 1 1 1 1

• 예제 출력

15

12

5

• 접근방식

중복되는 수를 체크하는 배열이 필요할 것으로 보이고 시작지점 startNumebr부터 시작해서 중복되는 수가 나오면 endNumber로 저장해두고 startNumber를 증가시키면서 경우의 수를 구하는 것으로 접근했다.
등차 수열의 합의 공식을 사용해서 n(n+1)/2를 더하면 된다.

• 코드

#include <iostream>
#include <algorithm>

using namespace std;

long long n, startNumber, endNumber, check[100004], a[100004], result;

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    while (endNumber < n)
    {
        if (!check[a[endNumber]])
        {
            check[a[endNumber]]++;
            endNumber++;
        }
        else
        {
            result += (endNumber - startNumber);
            check[a[startNumber]]--;
            startNumber++;
        }
    }
    
    result += (long long)(endNumber - startNumber) * (endNumber - startNumber + 1) / 2;
    cout << result;

    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/13144

• 문제

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

• 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

• 예제 입력

20

3

41

53

• 예제 출력

0

1

3

2

• 접근방식

소수를 먼저 구해야해서 에라스토테네스의 체를 사용했고, 구간을 정해야 하는데 low와 high을 사용한 투포인터로 구간을 정해서 구간들의 갯수가 해당 소수를 만들 수 있는 경우의 수이기 때문에 더하면 된다.

• 코드

#include <iostream>
#include <algorithm>

using namespace std;

bool check[4000001];
int n, a[2000001], p, low, high, result, sum;

int main()
{
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        if (check[i])    continue;
        for (int j = i * 2; j <= n; j += i)
        {
            check[j] = 1;
        }
    }

    for (int i = 2; i <= n; i++)
    {
        if (!check[i]) // 소수라면 집어넣기
        {
            a[p++] = i;
        }
    }

    while (1)
    {
        if (sum >= n) // low를 증가 시키는 조건
        {
            sum -= a[low++];
        }
        else if (high == p)  break;
        else // high을 증가 시키는 조건
        {
            sum += a[high++];
        }
        if (sum == n)
        {
            result++;
        }
    }

    cout << result;

    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1644

• 문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

• 출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

• 예제 입력

2 1
5 10
100 100
11

3 2
1 65
5 23
2 99
10
2

• 예제 출력

10

164

• 접근방식

우선, M과 V를 저장하는 벡터를 준비하고 가방의 최대 갯수를 저장하는 벡터를 준비한다.
두개의 벡터를 오름차순으로 정렬하고 가방에 들어갈 수 있는 보석을 찾고 PQ(우선순위 큐)에 넣어준다.
우선순위 큐는 내림차순으로 설정해주면 젤 위에 있는 값이 가장 가격이 높은 보석이기때문에 top만 결과에 넣어주고 pop하면 된다.
여기서 범위가 Ci의 경우 100,000,000까지 이기 때문에 long long 자료형을 사용해야한다.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

long long n, m, v, k, c, result;
vector<pair<int, int>> v1;
vector<int> v2;

int main()
{
    cin >> n >> k;

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

    for (int i = 0; i < k; i++)
    {
        cin >> c;
        v2.push_back(c);
    }

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    priority_queue<int> pq;
    int j = 0;
    for (int i = 0; i < k; i++) 
    {
        while (j < n && v1[j].first <= v2[i])
        {
            pq.push(v1[j++].second);
        }
        if (pq.size())
        {
            result += pq.top();
            pq.pop();
        }
    }
    cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1202

• 문제

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

• 입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

• 출력

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

• 예제 입력

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

• 예제 출력

4

• 접근방식

구간이 나오면 라인 스위핑을 생각하고 정렬을 먼저 했다. 정렬은 끝나는 시간을 기준으로 오름 차순으로 정렬하고 끝나는 시간이 시작 시간보다 크다면 다른 시간 탐색

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, startTime, endTime, result = 1;
vector<pair<int, int>> v;

int main()
{
    cin >> n;

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

    sort(v.begin(), v.end());

    startTime = v[0].second;
    endTime = v[0].first;

    for (int i = 1; i < n; i++)
    {
        if (v[i].second < endTime) continue; // 끝나는 시간이 시작 시간보다 더 크면 다른거 탐색 
        startTime = v[i].second;
        endTime = v[i].first;
        result++;
    }
    cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1931

• 문제

이웃 농장의 소가 길을 마구잡이로 건너는 것에 진절머리가 난 존은 극단의 결정을 내린다. 농장 둘레에 매우 큰 울타리를 짓는 것이다. 이렇게 하면 근처 농장 출신의 소가 들어올 일이 거의 없다. 이 일로 주변 소들이 분개하였다. 친구네 집에 놀러 갈 수 없을 뿐만 아니라, 매년 참가하던 국제 젖 짜기 올림피아드에도 올해는 참가할 수 없게 되었기 때문이다.

이웃 농장의 소 중 존의 농장에 방문할 수 있는 소가 조금 있긴 하지만, 그들도 안심할 수 있는 건 아니다. 존의 농장에 들어가는 문은 하나밖에 없고, 그 문을 통과하려면 감시관의 길고 긴 검문을 받아야 한다. 여러 마리의 소가 한 번에 들어가려고 하면 줄이 그 만큼 길어진다.

N마리의 소가 이 농장에 방문하러 왔다. 소가 도착한 시간과 검문받는 데 걸리는 시간은 소마다 다르다. (물론 같을 수도 있다.) 두 소가 동시에 검문을 받을 수는 없다. 예를 들어, 한 소가 5초에 도착했고 7초 동안 검문을 받으면, 8초에 도착한 그 다음 소는 12초까지 줄을 서야 검문을 받을 수 있다.

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

• 입력

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

• 출력

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

• 예제 입력

3
2 1
8 3
5 7

• 예제 출력

15

• 접근방식

라인 스위핑으로 접근했다. 스타트 지점을 기준으로 오름차순으로 정렬해서 처음에 시작한 좌표와 다음에 있는 좌표를 비교해서 max값을 구해서 그만큼 더해 준다.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, s, d;
vector<pair<int, int>> v;

int main()
{
    cin >> n;

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

    sort(v.begin(), v.end());

    int realtime = v[0].first + v[0].second;

    for (int i = 1; i < v.size(); i++)
    {
        realtime = max(realtime, v[i].first);
        realtime += v[i].second;
    }

    cout << realtime;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/14469

• 문제

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작은 자연수이다.

• 입력

첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

• 출력

첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

• 예제 입력

7
1 6
1 7
3 2
3 1
2 4
2 5
6 1

• 예제 출력

15

• 접근방식

데드 라인을 기준으로 오름 차순으로 정렬을 했다.

데드 라인이 같은 라면 갯수가 들어오면 최소 값을 제외하는 식으로 해결을 했다

이런 식으로 처음에는 크기가 1 이면 최소 값인 1, 2가 제외되고 크기가 2이면 최소 값인 3, 4가 제외가 되는 식으로 해결했다.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n, d, r, result;
vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
    cin >> n;

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

    sort(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++)
    {
        result += v[i].second;
        pq.push(v[i].second);
        if (pq.size() > v[i].first)
        {
            result -= pq.top();
            pq.pop();
        }
    }

    cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1781