백준 - 단어 공부(11399번)
문제
-
인하은행에는 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)
출력
- 첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.
이 문제에서 포인트는 오름차순으로 값을 누적해서 더하는 것이다.
코드 설계
문제 해결의 단계는 아래와 같다.
- 사람의 수를
N으로 입력받는다. 이때 사람의 수는 1000이하이다. - 각 사람의 시간을 배열
P에 저장한다. 그와 동시에check라는 배열을 0으로 초기화한다. 이 배열의 용도는 선택 여부이다. check가 0인 사람의 시간 중 최솟값min을 구한다. 이때min은 반복문 내에서 시간의 최댓값인 1000으로 초기화한다.- 사람 수만큼 반복문을 돌면서 누적 값을
sum으로 설정하고 총 합계를total로 설정하여 최종적으로total을 출력한다.
제출한 답
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
int N;
int P[1000];
int check[1000];
int sum = 0;
int total = 0;
int count = 0;
int index = 0;
// 사람 수 받기
scanf("%d", &N);
// 각 사람에 따른 시간 받기 + check 배열 초기화
for (int i = 0; i < N; i++) {
scanf("%d", &P[i]);
check[i] = 0;
}
while (count < N) {
++count;
int min = 1000;
for (int i = 0; i < N; i++) {
if ((min > P[i]) && (check[i] == 0)) {
min = P[i];
index = i;
}
}
check[index] = 1;
sum += min;
total += sum;
}
printf("%d", total);
}
💡한줄평
이 문제를 푸는데 다른 문제에 비해 많은 시간을 들이지 않았다. C 사용에 익숙해진 것인지 이 문제가 쉬웠던 것인지는 아직 판단이 되지 않는다. C언어는 시간이 짧게 걸리는 것이 장점인 것 같다. 그러나 추후 오름차순 정렬하는 알고리즘을 학습한 후 빅오 계산법을 활용해서 비교해보고 싶다.
