백준(BAEKJOOB) 11399번 ATM문제 c언어
문제
인하은행에는 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)
출력
첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.
먼저 5개를 입력 받고 배열을 저장시키기 위해서
밑에 코드 처럼 만들어주고
int people;
int i;
int s[1000];
scanf("%d", &people);
for (i = 0; i < people; i++) {
scanf("%d", &s[i]);
}
문제를 해석 해보면
1 2 3 4 5
3 1 4 3 2
1값에는 3이 저장되어 있고
2 값에는 1이 저장되어 있고
3 값에는 4가 저장되어 있고
4 값에는 3이 저장되어 있고
5 값에는 2가 저장되어 있다.
그러면 문제에서 합을 구하여라라고 하였기 때문에
1. 3
2. 3+1=4
3. 3+1+4=8
4. 3+1+4+3=11
5. 3+1+4+3+2=13
값들의 합은 39이다.
문제에서 힌트를 줬는데
2 5 1 4 3
1 2 3 3 4
이것 보다 최소 값은 없다고 하였다
그렇기 때문에 일단 밑에 수들을 정렬 해줘야된다.
범위가 1000이기 때문에 아무 정렬 알고리즘을 이용하여
for (i = 0; i < people; i++) { //
for(j=i+1; j<people; j++){
if (s[i] > s[j]) {
temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
}숫자들을 정렬해주고
※ 만약 정렬 알고리즘을 빼고 코드를
적을 경우 정렬되지 않고 답이 나오기 때문에
39가 나온다 최솟값이 아니기 때문에 문제에서 원하는 값이 나오지 않는다.
for (i = 0; i < people; i++) {
for (int j = 0; j <= i; j++)
{
sum = sum + s[j];
}
모든 숫자들을 더해서 sum값에 저장시킨다.
여기서 이중 반복문을 이용한 이유는 더한 숫자에 또 더해야 하기 때문에
이중 반복문이 필요한 것이다.
총 코드
#include<stdio.h>
//조건
int main() {
int people;
int i,j,temp;
int s[1000];
int sum = 0;
scanf("%d", &people);
for (i = 0; i < people; i++) {
scanf("%d", &s[i]);
}
for (i = 0; i < people; i++) { //
for(j=i+1; j<people; j++){
if (s[i] > s[j]) {
temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
}
for (i = 0; i < people; i++) {
for (int j = 0; j <= i; j++)
{
sum = sum + s[j];
}
}
printf("%d\n", sum);
}//main