[백준] 그리디 기초 문제풀이 ① - 5585, 11047, 11399, 2217 (C언어)

5585 거스름돈

문제

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

 

입력

입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

 

출력

제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

 

풀이

입력으로 들어온 수를 1000에서 빼고, 큰 화폐단위부터 차례대로 거슬러준다.

#include <stdio.h>

int main() {
    int n, result = 0;
    scanf("%d", &n);
    n = 1000-n;
    result += n/500;
    n%=500;
    result += n/100;
    n%=100;
    result += n/50;
    n%=50;
    result += n/10;
    n%=10;
    result += n/5;
    n%=5;
    result += n;

    printf("%d", result);

    return 0;
}

 

---

11047 동전 0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

풀이

배열에 화폐 단위를 넣어주고, 배열의 끝부터 돌면서 계산해준다.

#include <stdio.h>

int a[11]; // 화폐 단위

int main() {
    int n, k, result=0;
    scanf("%d %d", &n, &k);
    for(int i=0; i<n; i++) scanf("%d", &a[i]);

    for(int i=n-1; i>=0; i--) {
        result += k/a[i];
        k %= a[i];
    }
    printf("%d", result);

    return 0;
}

 

---

11399 ATM

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

 

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

 

풀이

걸리는 시간 Pi가 짧은 사람부터 순서대로 정렬한 뒤 시간의 합을 구하면 된다.
예제에서 3 1 4 3 2 가 주어지는데, 이를 오름차순으로 정렬하면 1 2 3 3 4가 되고 시간의 합은 1, 1+2, 1+2+3, 1+2+3+3, 1+2+3+3+4의 합이 되므로 p[i]*(n-i)를 더해서 누적시켜주면 된다.

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

using namespace std;

int p[1001];

int main() {
    int n, result=0;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &p[i]);
    sort(p, p+n);
    for(int i=0; i<n; i++) {
        result += p[i]*(n-i);
    }
    printf("%d", result);

    return 0;
}

 

---

2217 로프

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

 

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

 

출력

첫째 줄에 답을 출력한다.

 

풀이

(로프별 최대 중량 중에 가장 작은 값) * (로프 개수) = (들어올릴 수 있는 물체의 최대 중량)

이 때, 모든 로프를 사용할 필요는 없으므로 비교해보고 로프별 최대중량을 정렬한 후 작은 값부터 하나씩 빼면서 갱신하면 됨.

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

using namespace std;

int w[100001];

int main() {
    int n, max=0;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &w[i]);
    sort(w, w+n);
    for(int i=0; i<n; i++) {
        if (max < w[i]*(n-i)) max = w[i]*(n-i);
    }
    printf("%d", max);

    return 0;
}