[C] 백준 - 11399번: ATM

4월 3일(월)-그리디 알고리즘(11399번)

11399번: ATM

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- N을 입력받고, time배열에 N개의 돈을 인출하는데 걸리는 시간을 입력받는다

- 그리고나서 time 배열을 qsort를 이용해서 오름차순으로 정렬한다

- 오름차순으로 정렬된 time배열의 값들을, 각각의 순서에서 돈을 인출하는데 걸리는 누적 시간으로 바꾼다

- 이렇게 바꾸어놓은 time배열의 값들을 처음부터 끝까지 모두 sum 변수에 저장한뒤, 최종적으로 출력한다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

x

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(아래의 풀이로 정답을 얻어냈지만, 어느 부분에서 그리디 알고리즘을 활용하는 것인지 잘 모르겠다...

다른 풀이들을 찾아보더라도 마찬가지)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b)
{
	if (*(int*)a > *(int*)b)
	{
		return 1;
	}
	else if (*(int*)a < *(int*)b)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int main(void)
{
	int N;
	scanf("%d", &N);

	int time[1001];
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &time[i]);
	}
	qsort(time, N, sizeof(int), compare);

	for (int i = 1; i < N; i++)
	{
		time[i] = time[i - 1] + time[i];
	}

	int sum = 0;
	for (int i = 0; i < N; i++)
	{
		sum = sum + time[i];
	}

	printf("%d", sum);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

+)

반복문 2개로 나누어서 각각 시간값을 누적으로 더한 뒤, 그 후에 sum 값에 모든 값들을 다시 저장하던 것을

반복문 1개에서 시간값을 누적으로 더한 뒤, sum 값 저장을 동시에 진행하는 것도 가능하다

// 수정 전ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

	for (int i = 1; i < N; i++)
	{
		time[i] = time[i - 1] + time[i];
	}

	int sum = 0;
	for (int i = 0; i < N; i++)
	{
		sum = sum + time[i];
	}

// 수정 후ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

	int sum = time[0];
	for (int i = 1; i < N; i++)
	{
		time[i] = time[i - 1] + time[i];
		sum = sum + time[i];
	}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ