one step at a time

백준 - 2581 소수 ( https://www.acmicpc.net/problem/2581 )

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

예제 입력 1

60 
100

예제 출력 1

620
61

예제 입력 2

64 
65

예제 출력 2

-1

코드

#include <iostream>

using namespace std;

int main(){
    int n, m;
    scanf("%d %d", &n, &m);

    int sum = 0;
    bool min = false;
    int min_num;

    for(int i = n; i <= m; i++){
        bool prime = true;

        if (i < 2) prime = false;

        for(int j = 2;  j <= i/2; j++){
            if(i % j == 0){
                prime = false;
                break;
            }
        }

        if(prime == true){
            sum += i;
            if(min == false){
                min_num = i;
                min = true;
            }
        }
    }
    if (sum == 0){
        printf("-1\n");
    }
    else{
        printf("%d\n%d\n", sum, min_num);
    }
    return 0;
}

문제 설명

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다.

2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정합니다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정합니다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 됩니다. 각 지방에서 요청하는 예산이 담긴 배열 budgets과 총 예산 M이 매개변수로 주어질 때, 위의 조건을 모두 만족하는 상한액을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 지방의 수는 3 이상 100,000 이하인 자연수입니다.

• 각 지방에서 요청하는 예산은 1 이상 100,000 이하인 자연수입니다.

• 총 예산은 `지방의 수` 이상 1,000,000,000 이하인 자연수입니다.

입출력 예

문제 해결 방법

기본적인 이분 탐색 문제였다.

코드

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

using namespace std;

int solution(vector<int> budgets, int M) {
    int answer = 0;

    sort(budgets.begin(), budgets.end());
    int max = budgets.back();
    int min = 1;


    int d = 1000000000;

    while(max >= min){
        int mid = (max + min)/2;

        int sum = 0;

        for(int i = 0; i < budgets.size(); i++){
            if(budgets[i] <= mid){
                sum += budgets[i];
            }
            else{
                sum += mid;
            }
        }

        if(sum == M){
            answer = mid;
            break;
        }

        if(sum > M) {
            max = mid-1;
        }
        else{
            if(M-sum < d){
                answer = mid;
                d = M-sum;
            }
            min = mid + 1;
        }
    }
    return answer;
}

프로그래머스 - 섬 연결하기(https://programmers.co.kr/learn/courses/30/lessons/42861)

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.

• costs의 길이는 ((n-1) * n) / 2 이하입니다.

• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.

• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.

• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.

• 연결할 수 없는 섬은 주어지지 않습니다

입출력 예

입출력 예 설명

• costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

  

문제 해결 방법

한정점에서 모든 정점을 한번씩 거치는 최소 경로를 구하는 문제이다. 즉 MST(Minimun Spanning Tree)Algorithm 을 사용하면 문제가 풀린다. MST 알고리즘 중 Kruskal Algorithm을 사용해서 문제를 해결했다.

코드

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

using namespace std;

vector<int> node;

int getParent(int x){
    if(node[x] == x) return x;
    return node[x] = getParent(node[x]);
}

int find(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if( a == b) return 1; // 사이클이 존재한다.
    else return 0;
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a<b) node[b] = a;
    else node[a] = b;

}

bool compare(vector<int> a, vector<int> b){
    return a[2] < b[2];
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;

    sort(costs.begin(), costs.end(), compare);

    for(int i = 0; i < n; i++){
        node.push_back(i);
    }

    for(int i = 0; i < costs.size(); i++){
        if(!find(costs[i][0], costs[i][1])){
            answer += costs[i][2];
            unionParent( costs[i][0], costs[i][1]);

        }
    }


    return answer;
}

프로그래머스 - 구명보트(https://programmers.co.kr/learn/courses/30/lessons/42885)

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.

• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.

• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.

• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

입출력 예

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    for(int i = 0; i < people.size(); i++){
        int end = people.size();
        for(int j = end-1; j >= i; j--){
            if(people[i] + people[j] <= limit){

                people.pop_back();
                answer++;
                break;
            }
            else{

                people.pop_back();
                answer++;
            }

        }
    }
    return answer;
}

프로그래머스 - 기지국 설치(https://programmers.co.kr/learn/courses/30/lessons/12979)

문제 설명

N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다.

예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.)

• 초기에, 1, 2, 6, 7, 8, 9번째 아파트에는 전파가 전달되지 않습니다.

• 1, 7, 9번째 아파트 옥상에 기지국을 설치할 경우, 모든 아파트에 전파를 전달할 수 있습니다.

• 3개의 아파트보다 더 많은 아파트 옥상에 기지국을 설치할 경우에도 모든 아파트에 전파를 전달할 수 있습니다.

이때, 우리는 기지국을 최소로 설치하면서 모든 아파트에 전파를 전달하려고 합니다. 위의 예시에선 최소 3개의 아파트 옥상에 기지국을 설치해야 모든 아파트에 전파를 전달할 수 있습니다.

아파트의 개수 N, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W가 매개변수로 주어질 때, 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 리턴하는 solution 함수를 완성해주세요

제한사항

• N: 200,000,000 이하의 자연수

• stations의 크기: 10,000 이하의 자연수

• stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.

• W: 10,000 이하의 자연수입출력의 예

입출력 예

입출력 예 설명

입출력 예 #1 문제의 예시와 같습니다

입출력 예 #2

• 초기에, 1 ~ 6, 12 ~ 16번째 아파트에는 전파가 전달되지 않습니다.

• 3, 6, 14번째 아파트 옥상에 기지국을 설치할 경우 모든 아파트에 전파를 전달할 수 있습니다.

문제 해결 방법

주어지는 n의 크기가 200,000,000이라서 어떻게 문제를 풀어야 시간 초과가 나오지 않을지 모르겠어서 다른 코드를 참조해서 문제를 풀었다.( https://willbfine.tistory.com/381 )

왼쪽부터 전파가 닿지 않는 곳을 탐색하여 최대한 오른쪽에 기지국을 설치해 나가면서 문제를 풀면 된다.

코드

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


int solution(int n, vector<int> stations, int w)
{
    int answer = 0;

    int idx = 0;
    int location = 1;

    while(1){
        if(location > n){
            break;
        }

        if(idx < stations.size() && location >= stations[idx]-w){
            location = stations[idx] + w + 1;
            idx++;
        }
        else{
            location += 2*w + 1;
            answer++;
        }
    }

    return answer;
}

프로그래머스 - 배달 (https://programmers.co.kr/learn/courses/30/lessons/12978)

문제 설명

N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다.

위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 마을의 개수 N은 1 이상 50 이하의 자연수입니다.
• road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.
• road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
• road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
  • a, b(1 ≤ a, b ≤ N, a != b)는 도로가 연결하는 두 마을의 번호이며, c(1 ≤ c ≤ 10,000, c는 자연수)는 도로를 지나는데 걸리는 시간입니다.
  • 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
  • 한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
• K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
• 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
• 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

입출력의 예

입출력 예 설명

• 입출력 예 #1
  문제의 예시와 같습니다.

• 입출력 예 #2
  주어진 마을과 도로의 모양은 아래 그림과 같습니다.

  

  1번 마을에서 배달에 4시간 이하가 걸리는 마을은 [1, 2, 3, 5] 4개이므로 4를 return 합니다.

문제 해결 방법

한 정점에서 모든 정점의 최단 거리를 구하는 알고리즘인 Dijkstra Algorithm을 사용했다.

코드

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

using namespace std;

int INF = 10000000;

vector<pair<int, int>> map[51];
int result[51];

void dijkstra(int start){
    result[start] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(start, 0));

    while(!pq. empty()){
        int n = pq.top().first;
        int d = -pq.top().second;
        pq.pop();

        if(result[n] <d) continue;

        for(int i = 0; i < map[n].size(); i++){
            int n2 = map[n][i].first;
            int d2 = d + map[n][i].second;

            if(d2 < result[n2]){
                result[n2] = d2;
                pq.push(make_pair(n2, -d2));
            }
        }
    }
}

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;

    for(int i = 1; i <= N; i++){
        result[i] = INF;
    }

    for(int i = 0; i < road.size(); i++){
        int a = road[i][0];
        int b = road[i][1];
        int c = road[i][2];

        map[a].push_back(make_pair(b, c));
        map[b].push_back(make_pair(a, c));

    }

    dijkstra(1);

    for(int i = 1;  i <= N; i++){
        if(result[i] <= K){
            answer++;
        }
    }

    return answer;
}

프로그래머스 - 숫자 게임(https://programmers.co.kr/learn/courses/30/lessons/12987)

문제 설명

xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.

• 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.

• 각 사원은 딱 한 번씩 경기를 합니다.

• 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.

• 만약 숫자가 같다면 누구도 승점을 얻지 않습니다.

전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요. A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B가 주어질 때, B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.

제한사항

• A와 B의 길이는 같습니다.

• A와 B의 길이는 1 이상 100,000 이하입니다.

• A와 B의 각 원소는 1 이상 1,000,000,000 이하의 자연수입니다.

입출력의 예

입출력 예 설명

• 입출력 예 #1

  

  A 팀은 숫자 5를 부여받은 팀원이 첫번째로 출전하고, 이어서 1,3,7을 부여받은 팀원들이 차례대로 출전합니다. B 팀원들을 4번, 2번, 3번, 1번의 순서대로 출전시킬 경우 팀원들이 부여받은 숫자들은 차례대로 8,2,6,2가 됩니다. 그러면, 첫 번째, 두 번째, 세 번째 경기에서 승리하여 3점을 얻게 되고, 이때가 최대의 승점입니다.

  입출력 예 #2 B 팀원들을 어떤 순서로 출전시켜도 B팀의 승점은 0점입니다.

코드

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

using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());


    for(int i = 0; i < A.size(); i++){
        for(int j = i; j < B.size(); j++){

            if(B[j] > A[i]){
                answer++;
                B[j] = 0;
                break;
            }
        }
    }
    return answer;
}

프로그래머스 - 스킬트리(https://programmers.co.kr/learn/courses/30/lessons/49993)

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더 일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라으트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관 없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

제한사항

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.

• 스킬 순서와 스킬트리는 문자열로 표기합니다.

  • 예를 들어, C → B → D 라면 CBD로 표기합니다

• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.

• skill_trees는 길이 1 이상 20 이하인 배열입니다.

• skill_trees의 원소는 스킬을 나타내는 문자열입니다.

  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력의 예

입출력 예 설명

• BACDE: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.

• CBADF: 가능한 스킬트리입니다.

• AECB: 가능한 스킬트리입니다.

• BDA: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

bool find_c(char c, string s){
    for(int i = 0; i < s.length(); i++){
        if(s[i] == c){
            return true;
        }
    }
    return false;
}

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    for(int i = 0; i < skill_trees.size(); i++){

        int l = skill_trees[i].length();
        string temp = skill;
        bool check = true;

        for(int j = 0; j < l; j++){

            if(find_c(skill_trees[i][0], temp) == true){

                if(skill_trees[i][0] == temp[0]){
                    skill_trees[i].erase(skill_trees[i].begin());
                    temp.erase(temp.begin());
                }

                else{
                    check = false;
                    break;
                }
            }

            else{
                skill_trees[i].erase(skill_trees[i].begin());
            }

            if(temp.length() == 0){
                check = true;
                break;
            }
        }

        if(check == true){
            answer++;
        }

    }
    return answer;
}