[백준] 그리디 기초 문제풀이 ③ - 2437, 1783, 1969, 2812 (C/C++)

2437 저울

문제

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

 

입력

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

 

출력

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

 

풀이

저울추들을 정렬한 뒤 하나씩 더해나가면서 빈 공간이 있는지 확인한다.

핵심 아이디어는 측정 가능한 구간이 끊기지 않아야 한다는 것이다.

case 1) [1, 7] 구간이 측정 가능한 상황에 4kg 무게의 저울추가 추가로 주어지면, [1+4, 7+4]의 구간이 측정 가능해짐.
이는 [5, 11] 구간으로 기존의 구간과 합쳐져 [1, 11] 구간이 측정 가능해짐.

case 2) [1, 7] 구간이 측정 가능한 상황에 10kg 무게의 저울추가 추가로 주어지면, [11, 17] 구간이 추가로 측정 가능해짐.
즉 측정 가능 구간이 끊겼으므로 측정 불가한 무게의 최소값은 8kg

이처럼 다음 저울추의 무게가 측정 가능한 구간보다 작거나 같으면 끊기지 않고, 더 크면 끊긴다는 것을 알 수 있다.

 

정렬한 뒤 첫번째 저울추는 1이어야 하고, 두번째 저울추는 2와 같거나 작아야 한다.
첫번째, 두번째 저울추가 둘 다 1이면 측정 가능한 구간은 1~2고, 두번째 저울추가 2면 1~3이 된다.
그러므로 다음 검사할 저울추 무게는 첫번째 저울추 + 두번째 저울추 + 1이 된다.

즉,

1. 다음 저울추의 무게가 측정 가능한 구간의 최대값보다 작거나 같으면 끊기지 않고 검사가 가능하고

2. 다음에 검사할 저울추 무게는 측정 가능한 구간 + 비교한 저울추 무게(a[i]) + 1 이 된다.

핵심 아이디어는 측정 가능한 부분이 끊기지 위해서, 그 앞에서 측정 가능한 부분이 끊기지 않았다는 가정 하에
'다음 저울추의 무게'가 '측정가능한 구간 + 1'보다 작거나 같아야 한다는 것이다.

 

#include <stdio.h>
#include <algorithm>

using namespace std;

int a[1001];
int n, target = 1;

int main() {
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a+n);
    for(int i=0; i<n; i++) {
        if(target < a[i]) break;
        target += a[i];
    }
    printf("%d", target);

    return 0;
}

 

예제를 기준으로, 3 1 6 2 7 30 1을 정렬해 1 1 2 3 6 7 30 인 상태에서 1부터 만들 수 있는 수인지 검사해보자.

target = 1일 때: a[0]이 1보다 크면 만들 수 없다. target에 a[0]을 더해 다음을 검사한다. (만들 수 있는 구간: 1~1)
target = 2일 때: a[1]이 2보다 크면 만들 수 없다. target에 a[1]을 더해 다음을 검사한다. (만들 수 있는 구간: 1~2)
target = 3일 때: a[2]이 3보다 크면 만들 수 없다. target에 a[2]을 더해 다음을 검사한다. (만들 수 있는 구간: 1~4)
target = 5일 때: a[3]이 5보다 크면 만들 수 없다. target에 a[3]을 더해 다음을 검사한다. (만들 수 있는 구간 : 1~7)
target = 8일 때: a[4]이 8보다 크면 만들 수 없다. target에 a[4]을 더해 다음을 검사한다. (만들 수 있는 구간 : 1~13)
target = 14일 때: a[5]이 14보다 크면 만들 수 없다. target에 a[5]을 더해 다음을 검사한다. (만들 수 있는 구간 : 1~20)
target = 21일 때: a[6]이 21보다 크면 만들 수 없다. a[6]이 target보다 작으므로 target을 반환하고 종료한다.

 

---

1783 병든 나이트

문제

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

 

입력

첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

 

출력

병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.

 

풀이

이동횟수가 4 이상이면 모든 방법을 한번씩 사용해야 하고, 이동횟수가 3 이하면 이동방법 사용 횟수에 제약이 없음을 유의해 케이스를 분류한다.

 i) 높이 n == 1

가로 m이 몇이든 시작지점 하나밖에 방문하지 못한다.

ii) 높이 n == 2

2, 3 방법으로 오른쪽으로 2칸씩만 이동할 수 있다. (1, 3, 5, 7, ...) 

가로가 7 이하일 때는 (m+1)/2 방문 가능
가로가 8 이상일 때는 3번 이동, 즉 4개 방문이 최대

ii) 높이 n == 3

2,3을 사용하는 것보다 1,4를 이용해 가는 것이 더 많은 지점을 방문할 수 있다.

가로 4까지는 m
가로 5~6이면 최대 4
가로 7부터는 2,3을 한번씩만 사용하고 나머지는 1,4로 이동하면 되므로 m-2

#include <iostream>

using namespace std;

int n, m;

int main() {
    scanf("%d %d", &n ,&m);
    if(n == 1) printf("1");
    else if(n == 2) {
        printf("%d", min((m+1)/2, 4));
    }
    else {
        if (m >=7) printf("%d", m-2);
        else printf("%d", min(m, 4));
    }

    return 0;
}

 

---

1969 DNA

문제

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자를 따서 표현한다. 만약에 Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-Cytosine-Cytosine-Guanine-Adenine-Thymine로 이루어진 DNA가 있다고 하면, “TAACTGCCGAT”로 표현할 수 있다. 그리고 Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클오티드 문자가 다른 것의 개수이다. 만약에 “AGCAT"와 ”GGAAT"는 첫 번째 글자와 세 번째 글자가 다르므로 Hamming Distance는 2이다.

우리가 할 일은 다음과 같다. N개의 길이 M인 DNA s1, s2, ..., sn가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 s1의 Hamming Distance + s와 s2의 Hamming Distance + s와 s3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

 

입력

첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

 

풀이

가장 많이 등장한 문자를 세서 문자열로 만들어준다. n에 대한 포문을 돌며 각 자리를 검사할 때 전체 횟수(n)에서 등장한 횟수를 빼면 그 자리에 대한 hamming distance가 된다.

참고로 min을 갱신할 때 min 보다 작을 때만 갱신하게 해주어서, 사전순으로 가장 앞서는 것이 등록되게끔 했다.

 

#include <iostream>
#include <string>

using namespace std;

int n, m, dist;
string s;
string a[1001];

int main() {
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++) {
        cin >> a[i];
    }
    for(int i=0; i<m; i++) {
        int cnt[4] = {0, };
        for(int j=0; j<n; j++) {
            if(a[j][i] == 'A') cnt[0]++;
            if(a[j][i] == 'C') cnt[1]++;
            if(a[j][i] == 'G') cnt[2]++;
            if(a[j][i] == 'T') cnt[3]++;
        }
        int idx=0, min=1001;
        for(int j=0; j<4; j++) {
            if (min > n - cnt[j]) {
                min = n - cnt[j];
                idx = j;
            }
        }
        if(idx == 0) s += 'A';
        if(idx == 1) s += 'C';
        if(idx == 2) s += 'G';
        if(idx == 3) s += 'T';
        dist += min;
    }
    cout << s << endl << dist;

    return 0;
}

 

---

2812 크게 만들기

문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

 

입력

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

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

 

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

 

풀이

맨 앞자리 수가 클수록 큰 수이므로 앞에 있는 수보다 뒤에 들어오는 수가 더 크면 앞에 있는 수를 지워주면 된다.

만약 포문을 다 돌았는데 지울 수가 남아있다면 이미 내림차순이 되어 있는 상태이므로 뒤에서부터 지워준다.

#include <iostream>
#include <vector>

using namespace std;

int n, k;   // 길이, 지워야하는 개수
string a;
vector<char> result;

int main() {
    scanf("%d %d", &n, &k);
    cin >> a;
    for(int i=0; i<n; i++) {
        while(k > 0 && !result.empty() && result.back() < a[i]) {
            result.pop_back();
            k--;
        }
        result.push_back(a[i]);
    }
    while(k--) result.pop_back();
    
    for(int i=0; i<result.size(); i++) cout << result[i];

    return 0;
}