[BOJ] C++ 그리디 알고리즘 문제풀이 (2)

🧨 백준 11399번

문제 출처 : 백준 11399번 - ATM

문제 난이도 : 실버3

문제 링크 : www.acmicpc.net/problem/11399

11399번: ATM

🧨 알고리즘 선택 및 C++ 코드

이 문제 푸는데 OS의 프로세스 순서 정하는 알고리즘이 문득 생각났다.. 수행시간이 짧은 걸 먼저 실행시키면 starvation(기아)이 발생할 수밖에 없다는 문제가 있었는데,, 어쨌든 그리디로 풀어보았다. 각 자리수까지의 sum을 저장할 배열을 또 만들 수도 있지만 괜히 저장공간을 더 쓰고싶지 않았다.

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

using namespace std;

#define MAX 1001

int main()
{
    int N;
    scanf("%d", &N);
    vector<int> P(N);
    for(int i = 0; i < N; i++) {
        scanf("%d", &P[i]);
    }
    
    sort(begin(P), end(P));
    
    int target = 0;
    for(int i = 0; i < N; i++) {
        target += P[i] * (N - i);
    }
    
    printf("%d", target);
    
    return 0;
}

---

 

🧨 백준 2217번

문제 출처 : 백준 2217번 - 로프

문제 난이도 : 실버4

문제 링크 : www.acmicpc.net/problem/2217

2217번: 로프

🧨 알고리즘 선택 및 C++ 코드

역시나 그리디 알고리즘을 이용한 문제는 머리로 생각한 걸 코드로 구현해내기가 조금 막막하다. 일단 로프 중량을 오름차순 정렬하고 작은 것부터 중량을 늘려가며 총 중량(maxweight)을 비교한다. 보통 그리디 알고리즘은 큰 단위부터 계산했는데(ex. 동전문제) 이 문제에서는 큰 단위부터 계산하면 안 된다. 머리를 굴리자..!

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

using namespace std;

#define MAX 1001

int main()
{
    int N;
    scanf("%d", &N);
    vector<int> rope(N);
    for(int i = 0; i < N; i++) {
        scanf("%d", &rope[i]);
    }
    
    sort(begin(rope), end(rope));
    
    int maxweight = 0;
    // 가장 작은 중량 * 로프 개수 에서부터 중량은 늘려가고 
    // 로프개수는 줄여나가면서 총 중량을 비교한다
    for(int i = 0; i < N; i++) {
        int weight = rope[i] * (N - i);
        if(maxweight < weight) {
            maxweight = weight;
        }
    }
    
    printf("%d", maxweight);
    
    return 0;
}

 

---

🧨 백준 13458번

문제 출처 : 백준 13458번 - 시험감독

문제 난이도 : 브론즈2

문제 링크 : www.acmicpc.net/problem/13458

13458번: 시험 감독

🧨 알고리즘 선택 및 C++ 코드

브론즈2라서 만만하게 봤다가 정답율이 왜 25퍼인지 깨달았다. 분명 논리로는 내 코드가 맞는 거 같은데 자꾸 틀렸다길래 게시판에 사람들 질문한 걸 살짝 봤더니 long long 으로 선언해줘야 한다는 내용이 있었다. 처음엔.. 이게 그냥 int 형 안에서 노는 거 아닌가 싶었는데.. 보다보니 최종 sum 값은 long long 이 될 수도 있겠더라. 시험장 개수가 N(1 ≤ N ≤ 1,000,000) 100만이고, 시험장의 응시자 수가 Ai (1 ≤ Ai ≤ 1,000,000) 최대 100만이다. 감독관이 감독할 수 있는 최소 인원이 1명이니 잘못하면 100만 * 100만 명의 감독관이 필요할 수도 있겠다. 1 0000 0000 0000 이니까 int 형으로 못 담아낸다. 그럼 무조건 항상 long long 형을 쓸까도 싶었는데 그럼 연산 속도가 느려진다.. 앞으로는 데이터타입도 다시 한번 따져 볼 것..

코드는 좀 더러운 거 같다. 하지만 다시 줄일 생각은 없음..

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

int main()
{
    int N;
    int B, C;
    scanf("%d", &N);
    vector<int> student(N);
    for(int i = 0; i < N; i++) {
        scanf("%d", &student[i]);
    }
    scanf("%d %d", &B, &C);
    
    long long sum = 0;
    for(int i = 0; i < N; i++) {
        int classsum = 1;
        if(student[i] <= B) {
            sum += classsum;
            continue;
        } else {
            student[i] -= B;
            classsum += student[i] / C;
            if(student[i] % C) classsum++;
            sum += classsum;
        }
    }
    
    printf("%lld", sum);
    
    return 0;
}