[C] 백준 - 1049번: 기타줄

8월 23일(수) - 그리디 알고리즘 (1049번)

1049번: 기타줄

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

 

최초 생각 정리

- 입력은 사야하는 기타줄의 개수 N, 브랜드의 종류 M을 입력받는다

   또한, 각각의 브랜드별로 패키지가격과 낱개의가격을 각각 변수 package, 변수 single에 입력받는다

- 1) 패키지는 전혀없이 낱개로만 구매하는 경우 -> final_min 계산

   2) 패키지를 구매해야하는 경우

       2-1) N이 6의 배수가 아니라서 나머지가 생기는 경우

              3-1) 나머지를 패키지로 퉁쳐서 사는게 저렴한 경우 -> final_min 계산

              3-2) 나머지를 낱개로 사는게 저렴한 경우 -> final_min 계산

       2-2) 나머지가 생기지 않는 경우 ->  final_min 계산

  위와 같은 구성으로 if - else문의 분기점을 나눈다

- 출력은 변수 final_min을 출력한다

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

 

문제점

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

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

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

	int min_package = 1000;
	int min_single = 1000;

	int package, single;
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &package, &single);

		if (package < min_package)
		{
			min_package = package;
		}
		if (single < min_single)
		{
			min_single = single;
		}
	}

	int final_min = 0;
	if (min_single * 6 <= min_package)
	{
		final_min = min_single * N;
	}
	else
	{
		final_min = (N / 6) * min_package;

		if (N % 6 != 0)
		{
			if (min_package < min_single * (N % 6))
			{
				final_min = final_min + min_package;
			}
			else
			{
				final_min = final_min + min_single * (N % 6);
			}
		}
	}

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

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

 

풀이 - 2

(230830 추가 -> 자바로 풀이하며 추가)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int MIN(int x, int y)
{
	return ((x < y) ? (x) : (y));
}

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

	int min_6 = 1000;
	int min_1 = 1000;

	int package, single;
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &package, &single);

		min_6 = MIN(min_6, package);
		min_1 = MIN(min_1, single);
	}

	int price = 987654321;
	price = MIN(price, (N / 6 + 1) * min_6);
	price = MIN(price, min_1 * N);
	price = MIN(price, (N / 6) * min_6 + (N % 6) * min_1);

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

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