[백준알고리즘] 11399번: ATM -C, Python

[백준알고리즘] 11399번: ATM -C, Python

https://www.acmicpc.net/problem/11399

11399번: ATM

 

그리디 알고리즘의 대표적인 예라고 생각하는 문제이다.

이 문제는 CPU scheduling 기법 중 하나인 SJF(Shortest Job First)을 알고 있다면 쉽게 풀 수 있는 문제이다.

 

 

이 문제도 마찬가지로 처리시간이 짧은 순서대로 정렬을 해서 처리를 해주면 된다.

 

다른 분들은 이 부분을 위해서 시간복잡도가 빠른 퀵 정렬 등을 사용해서 정렬을 해주었지만, 여기서 배열을 이용해서 바로 이용하려고 한다. 즉, 정렬 알고리즘 없이 두 개의 배열을 두고 이용할 것이다. t의 처리시간을 갖는 사람이 있다면 P[t]를 갖는 사람이 존재하는 것이기 때문에 P[t]를 증가시켜준다.

 

전부 사람들을 각각 갖는 처리시간에 맞게 넣어준 후 다시 처음(P[0])부터 진행하면서 해당 처리시간을 갖는 사람이 있을 때 순서대로 그 사람이 갖게 되는 "(대기시간) + (처리시간)"을 계산해서 다른 배열 time[]에 순서대로 넣어준다. 그렇게 되면 time[]에는 작은 처리시간을 갖는 사람부터 순서대로 각 사람이 갖는 "(대기시간) + (처리시간)"을 갖고있게 된다.

 

마지막에 time[]배열을 모두 더해주면 우리가 원하던 값을 얻게 될 것이다.

 

 

처음에는 시간초과도 아니고 틀렸다고 나와서 무엇이 틀렸는지 골치아팠는데 범위를 잘못줬었다. P의 범위를 1000으로 줘놓고 1001로 주고 실제 인덱스값으로 하는 것처럼 해서 나타난 문제였다. 코드는 아래와 같다.

 

#include <stdio.h>

int main(void){
    int N, i, t, sum;
    int P[1001] = {0};
    int time[1000] = {0};
    
    /* input */
    scanf("%d", &N);
    for(i = 0; i < N; i++){
        scanf("%d", &t);
        P[t]++;
    }

    /* solve */
    sum = 0;
    t = 0;
    for(i = 1; i < 1001; i++){
        while(P[i] > 0){
            sum += i;
            time[t] = sum;
            t++;

            P[i]--;
        }
    }

    /* output */
    sum = 0;
    for(i = 0; i < N; i++) 
        sum += time[i];

    printf("%d\n", sum);

    return 0;
}

 

2020.03.06

풀려있던 걸 새로 풀었는데 C로 풀었을 줄은 몰랐따.

암튼 파이썬으로도 문제를 풀어서 코드를 첨부하기로 했다.

 

import sys
n = int(sys.stdin.readline())
time = list(map(int, sys.stdin.readline().split()))
time.sort()
for i in range(1, len(time)):
    time[i] += time[i-1]
print(sum(time))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다