[백준/C++] 1049번. 기타줄

문제

1049번: 기타줄

---

1. 첫 번째 풀이

사고 과정

- 브랜드 개수는 눈속임. 결국 제일 싼 걸 살 것이다.

- 입력되는 값들 중 가장 싼 패키지 / 가장 싼 낱개 가격만 따로 저장

- 낱개 x 6이 패키지보다 싸다면 오직 낱개로만, 아니라면 패키지로 구매한 후

- 남은 사야 할 줄이 6개 이하일 때 패키지와 낱개 x 6 가격을 비교, 저렴한 걸 선택한다.

 

1. 알고리즘을 정리하여

2. 숫자에 맞춰 작성

 

이후 작성할 글이 있다면 추가 작성

 

코드

#include <iostream>

int main() {
	int	N, M, p, o, pack = 1000, one = 1000;

	std::cin >> N >> M;

	// 가장 저렴한 패키지, 낱개 저장
	while (M--) {
		std::cin >> p >> o;
		pack = (p < pack) ? p : pack;
		one = (o < one) ? o : one;
	}

	// 낱개가 패키지보다 저렴하다면 낱개로만 구매
	if (one * 6 < pack) {
		std::cout << one * 6;
		return 0;
	}

	// 패키지 구매
	int price = pack * (N / 6);
	N %= 6;

	// 패키지와 낱개 중 저렴한 걸 선택
	if (one * N < pack) {
		price += one * N;
	}

	else {
		price += pack;
	}

	std::cout << price;

	return 0;
}

 

결과

결과는 오답

---

2. 두 번째 풀이 (마지막 풀이)

사고 과정

- 첫번째로 찾은 건, 낱개로만 계산할 때 출력을 잘못 넣은 부분. N개를 사야 하는데 6개만 구매했다.

- 낱개 6개와 패키지 가격이 같을 때도 낱개로만 구매하면 되니 조건을 < 에서 <= 로 변경했다.

- 패키지가 더 저렴한 경우엔 문제가 없으니, 다시 넣어보았다.

 

코드

#include <iostream>

int main() {
	int	N, M, p, o, pack = 1000, one = 1000;

	std::cin >> N >> M;

	while (M--) {
		std::cin >> p >> o;
		pack = (p < pack) ? p : pack;
		one = (o < one) ? o : one;
	}

	if (one * 6 <= pack) {
		std::cout << one * N;
		return 0;
	}

	int price = pack * (N / 6);
	N %= 6;

	if (one * N < pack) {
		price += one * N;
	}

	else {
		price += pack;
	}

	std::cout << price;

	return 0;
}

 

결과

성공했다. 

---

개선

사고 과정

- 선택하는 부분을 따로 함수로 빼면 어떨까?

- 함수만 따로 재사용할 수도 있고, 위처럼 출력 후 반환할 필요가 없으니 사용도 더 간편해질 것이다.

- 가독성을 높이기 위해 패키지 구매 후 남은 줄을 구매하는 과정에서, if (pack < one * 6)으로 변경하였다. 사소한 차이지만 조금 더 의미가 와닿는다.

- 함수 내부의 if문을 삼항 조건문으로 축약할 수 있어보인다. 총 7줄의 코드가 1줄로 줄어들었다.

코드

#include <iostream>

int getMinPrice(int N, int pack, int one) {
	if (one * 6 <= pack) {
		return one * N;
	}

	int price = pack * (N / 6);

	N %= 6;

	price += (pack < one* N) ? pack : one * N;

	return price;
}

int main() {
	int N, M, p, o, pack = 1000, one = 1000;

	std::cin >> N >> M;

	while (M--) {
		std::cin >> p >> o;
		pack = (p < pack) ? p : pack;
		one = (o < one) ? o : one;
	}

	std::cout << getMinPrice(N, pack, one);

	return 0;
}

코드 길이는 약간 늘어났지만, 더 이해하기 쉬워졌다.

 

결과

결과는 역시나 성공

---

가장 효율적인 코드

https://www.acmicpc.net/source/1200553

whdgnsdl887님의 코드. 13줄 안에 나와 같은 로직이 들어있다.

 

내 코드와 비교

1. cin 대신 scanf를 사용하셨다. scanf가 속도도 더 빠르고 유용한 점이 많아서 그런 듯하다.

2. 패키지 가격에 삼항 조건문을 사용해 값을 변경. 낱개 * 6이 더 저렴하다면 패키지 가격으로 바꿔버렸다.

3. 내가 작성한 getMinPrice 부분도 한 줄 출력으로 끝내셨다. 원리는 동일하다. 내가 마지막에 if else 문을 삼항 조건문 하나로 줄인 것처럼, 패키지를 구매하고 남은 줄 역시 낱개 * 줄 개수와 패키지 중 저렴한 것을 택한 것.

 

if문을 극한으로 줄이면 이렇게까지 줄일  수 있다! 는 듯한 코드다. 실제로 작성 속도도 빨라지고, 띄어쓰기만 적절하다면 의미 파악도 수월할 것 같다. if문을 작성하기 전에 삼항 조건문으로 통합이 가능한 지, 한 번 더 생각해 봐야겠다.

---

강평

문제 자체는 어렵지 않았지만, '어떻게 하면 더 간결하게 쓸 수 있을까?'를 고민할 수 있는 그리디 문제다. 티어도 실버 4정도로 그리 어렵지 않다. 어려운 문제들은 직접 알고리즘을 생각해보는 부분이, 쉬운 문제들은 다른 분들의 코드를 보며 어떻게 간결하게 쓸 수 있는지 배울 수 있다.