[백준] 11047번 문제풀이

문제 : www.acmicpc.net/problem/11047

기존에는 - 하는 형식으로 알고리즘을 구성했었다.

코드는 이와 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main(void)
{
	int n, k;
	int arr[10];
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	int count = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		int temp = k - arr[i];
		if (temp >= 0) {
			k -= arr[i];
			count++;
			i++;
		}
	}

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

근데 왠걸 K 의 입력범위가 1<=K<=100000000 이다. 그래서 실행속도가 너무 많이나온다.

따라서 이와 같이 바꿔보았다.

 

바뀐건 몇줄 없지만 시간이 엄청나게 단축 되었다.

4200원이 K 라면, 1000원 4개와 100원 2개가 있으면 만족한다.

기존에는 4200 -> 3200 -> 2200 -> 1200 -> 200 -> 100 -> 0 이런식이었다면,

현재는 4200 -> 200 -> 0 으로 계산을 한다.

코드는 아래와 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main(void)
{
	int n, k;
	int arr[10];
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	int count = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		int temp = k / arr[i];
		if (temp > 0) {
			k -= arr[i] * temp;
			count += temp;
		}
	}

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

걸린시간 : 15분정도?