[백준] 그리디 기초 문제풀이 ② - 1138, 1541, 10610, 1946 (C/C++)

1138 한 줄로 서기

문제

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

 

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

 

풀이

모든 사람에 대해 왼쪽부터 하나씩 살펴보며 자신이 들어갈 수 있는 위치를 고른다.

자리가 비어있으면 자신보다 큰 사람이 올 자리이므로, 들어왔던 수를 하나씩 줄여 0이 되었을 때 그 자리가 비어있으면 넣는다.

#include <stdio.h>

int a[11];

int main() {
    int n, tmp, idx=0;
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d", &tmp);
        for(int j=0; j<n; j++) {
            if (tmp == 0 && a[j] == 0) {
                a[j] = i+1;
                break;
            }
            if (tmp > 0 && a[j] == 0) tmp--;
        }
    }

    for(int i=0; i<n; i++) printf("%d ", a[i]);
    return 0;
}

 

---

1541 잃어버린 괄호

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

 

출력

첫째 줄에 정답을 출력한다.

 

풀이

마이너스가 한번이라도 등장한 시점부터는 그 뒤로 이어진 모든 숫자들은 마이너스로 처리할 수 있다는 특징을 이해해야 한다.

마이너스 등장 전 숫자들은 모두 양수로, 등장 후 숫자들은 모두 음수로 더해주면 된다.

#include <iostream>
#include <string>

using namespace std;

string a;

int main() {
    cin >> a;
    int result=0;
    bool minus=false;
    string tmp= "";
    for(int i=0; i<=a.size(); i++) {
        if(a[i] == '-' || a[i] == '+' || a[i] == '\0') {
            if (minus) result += -stoi(tmp);
            else result += stoi(tmp);
            tmp = "";
            if (a[i] == '-') minus = true;
        }
        else tmp += a[i];
    }
    printf("%d", result);

    return 0;
}

 

---

10610 30

문제

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

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

 

입력

N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

 

출력

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

 

풀이

각 자리수의 합이 3이면 3의 배수가 되는 특징이 있다. 30의 배수여야 하므로 0이 포함되어있어야 함을 유의해서 풀면 된다.

각 자리수를 담은 배열을 만들고, string으로 받아 정수로 바꿔주며 자리수가 출현한 빈도를 세면 간단하게 풀 수 있다.

#include <iostream>
#include <string>

using namespace std;

int number[10];

int main() {
    string a;
    cin >> a;
    int tmp=0;
    for(int i=0; i<a.size(); i++) {
        number[a[i]-'0']++;
        tmp+=a[i]-'0';
    }
    if(number[0]==0 || tmp%3 != 0) printf("%d", -1);
    else {
        for(int i=9; i>=0; i--) {
            for(int j=0; j<number[i]; j++) printf("%d", i);
        }
    }

    return 0;
}

 

---

1946 신입사원

문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

 

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

 

풀이

서류순위 기준으로 오름차순 정렬 후, 면접순위를 기준으로 앞에서부터 면접순위 최솟값을 갱신하면서 카운트를 센다.

즉, 서류순위가 낮으면 면접순위는 (면접순위)최솟값보다 더 높아야 하는 것이다.

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

using namespace std;

vector<pair<int, int>> v;

int main() {
    int t, n;
    scanf("%d", &t);
    while(t--) {
        v.clear();
        int min = 100001, result = 0;
        scanf("%d", &n);
        for(int i=0; i<n; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            v.push_back(make_pair(x, y));
        }
        sort(v.begin(), v.end());
        for(int i=0; i<n; i++) {
            if(min > v[i].second) {
                min = v[i].second;
                result++;
            }
        }
        printf("%d\n", result);
    }

    return 0;
}