[백준] 18185번 - 라면 사기 (Small) (C++)

18185번: 라면 사기 (Small)

문제

라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).

교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다.

1. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.
2. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N1). 이 경우 비용은 5원이 든다.
3. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N2). 이 경우 비용은 7원이 든다.

최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 라면 공장의 개수를 의미하는 자연수 N가 주어진다.

두번째 줄에 N개의 정수 A1, ···, AN가 사이에 공백을 두고 주어진다.

---

출력

첫 번째 줄에 교준이가 필요한 최소 금액을 출력한다.

---

제한

모든 입력 데이터는 다음 조건을 만족한다.

• 3 ≤ N ≤ 10^4
• 0 ≤ Ai ≤ 10^4 (1 ≤ i ≤ N)

---

예제 입력 1

3
1 0 1

예제 출력 1

6

예제 입력 2

5
1 1 1 0 2

예제 출력 2

13

---

풀이과정

문제의 알고리즘 분야가 그리디알고리즘이다보니 일단 내용을 정리하고 점화식을 세우는것에 집중해보았습니다.

기본적으로 문제의 조건이

1. A[i] 라면 구매 = 3원
2. A[i], A[i+1] 라면 구매 = 5원
3. A[i], A[i+1], A[i+2] 라면 구매 = 7원

라는 기본전제 조건으로 깔려있어서 해당 내용을 바탕으로 점화식을 계산하게 되었습니다.

점화식을 구성하면서 신경쓰였던 부분들이

1. [2] [0] [2] 이러한 식으로 값이 들어올때 3번방식으로 2번 구매하는게 이득인가 1번방식으로 4번 구매하는게 이득인가?
   [2] [0] [2] 이러한 식으로 값이 들어올때 3번방식으로 2번 구매하는게 이득인가 1번방식으로 4번 구매하는게 이득일까를
   고민했었을때는 7 * 2 = 14 , 3 * 4 = 12 이므로 값이 연달아 되어있지않다면 따로사는게 이득이다라는 라는 결론이 나왔었다.
2. 무조건 라면공장이 연달아 이어져있다면 한번에 3개 사는게 이득인가?
   해당 조건에 대해서는 처음에는 당연히 3개를 사는게 훨씬 이득이니까 3개를 한번에 사야되지않나 라고 생각을 하고 코드를 구성했었는데 문제의 키 포인트가 되는 반례가 있었다. ( 추후 설명 )
3. 어떠한 경우에 라면을 구매해야하는가?
   기본적으로 라면은 한번에 많이 구매할수록 이득이므로 3, 2, 1개 순으로 라면의 개수를 확인한다. 현재 검사하는 값 기준으로 A[i], A[i+1], A[i+2] 이 3가지가 모두 값을 가지고 있다면 구매를 하고 그 다음은 A[i], A[i+1] 2가지가 값을 가지고 있다면 구매를 하고 A[i] 가 값을 가지고 있다면 구매를 하는 방식으로 차근 차근 현재 검사하는 값 기준으로 모든 값을 구매하고 넘어가는 방식으로 코드를 작성하였다.

#include <iostream>
#include <algorithm>

int		main(void)
{
	int		n, temp, money, a[10001] = {0};

	std::cin >> n;
	money = 0;
	for(int i = 0; i < n; i++)
		std::cin >> a[i];
	for(int i = n - 1; i >= 0; i--) {
		if (a[i] > 0) {
			if (0 < a[i] && 0 < a[i-1] && 0 < a[i-2]) {
				temp = std::min(std::min(a[i], a[i-1]), a[i-2]);
				money += (7 * temp);
				a[i-2] -= temp;
				a[i-1] -= temp;
				a[i] -= temp;
			}
			if (0 < a[i] && 0 < a[i-1]) {
				temp = std::min(a[i], a[i-1]);
				money += (5 * temp);
				a[i-1] -= temp;
				a[i] = temp;
			}
			if (0 < a[i]) {
				money += (3 * a[i]);
				a[i] = 0;
			}
		}
	}
	std::cout << money;

	return (0);
}

위에서 세워두었던 식대로 코드를 구성했었는데 틀렸다라는 결과를 받을 수 있었다. 그래서 왜 틀렸을까 고민을 많이 했었는데

글 읽기 - 틀렸습니다. 반례 케이스

라는 반례가 있다는 것을 찾게 되었다. 저 글에서 이야기하는 방식은 입력값이

4

2 3 2 1

형식으로 들어오게 될때 처리방식이 항상 3개를 우선으로 처리하는 방식을 쓰게 되면

[2] [3] [2] [1]

[1] [2] [1] [1]

[0] [1] [0] [1]

[0] [0] [0] [1]

[0] [0] [0] [0]

인 방식으로 7 + 7 + 3 + 3 으로 총 20이라는 값이 들어가게 되고

 

[2] [3] [2] [1]

[1] [2] [1] [1]

[0] [1] [1] [1]

[0] [0] [0] [0]

중간에 2개가 연달아 있는경우를 3개가 연달아 있는경우보다 상황에 따라 먼저 처리를 하게 된다면 7 + 5 + 7 = 19 로 더 작은 값을 구할 수 있게 된다.

그래서 저런 반례 케이스를 추가적으로 수정해주는 작업을 해줄필요가 있어보였다.

3개가 연달아 있는 경우에 3개를 바로바로 없애는 방식을 사용하게 되면 [1] [0] [1] 같은 연결선이 끊어지는 경우가 발생될 수 있어서

A[i + 1] 보다 A[i + 2] 이 크거나 같은 경우에만 3개씩 먼저 없애는 일을 진행하는 식으로 코드를 변환하여 제출을 하였더니 문제를 해결할 수 있었다.

code

#include <iostream>
#include <algorithm>

int		main(void)
{
	int		n, money, a[10001] = {0};

	std::cin >> n;
	money = 0;
	for(int i = 0; i < n; i++)
		std::cin >> a[i];
	for(int i = 0; i < n; i++) {
		while (0 < a[i]) {
			if (a[i+1] <= a[i+2] && 0 < a[i] && 0 < a[i+1] && 0 < a[i+2]) {
				money += 7;
				a[i+2]--;
				a[i+1]--;
				a[i]--;
			}
			else if (0 < a[i] && 0 < a[i+1]) {
				money += 5;
				a[i+1]--;
				a[i]--;
			}
			else if (0 < a[i]) {
				money += 3;
				a[i]--;
			}
		}
	}
	std::cout << money;

	return (0);
}

 

---

후기

“백준 상위 문제는 얼마나 어려울까”라는 궁금증에서 시작하게 되어 문제를 쭈욱 돌아보다가 그 나마 문제가 접근할만 한거같아서 문제를 풀어보게 되었습니다.

문제가 다이아인만큼 확실히 점화식을 세우는게 어려웠던 거 같습니다.