[D5] 백준 18185번 라면 사기(Small) C++ 그리디 알고리즘

리뷰

 

되게 쉬워보이면서도 조건이 까다로워 풀기가 어려웠던 문제

https://www.acmicpc.net/problem/18185

 

 

전역 변수

• n, ans : 공장의 개수를 저장할 정수형 변수 n, 정답을 저장할 정수형 변수 ans
• nodes : 공장 정보를 입력 받을 정수형 배열, 공장의 최대값 10000보다 2가 크게 크기를 설정한다.

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 공장 정보를 nodes배열에 저장해 준다.
2. 다시 n번의 for문을 수행한다, 만약 nodes[i]가 0이라면 continue 처리해 준다.
3. 만약 nodes[i + 1]이 nodes[i + 2]보다 크다면 2개를 사는 것과 3개를 사는 것을 조건부로 처리해 줘야 한다.
4. 먼저 nodes[i]와 nodes[i + 1]중 최소값 만큼만 두 공장에서 구매를 한다.
5. 이후 nodes[i], nodes[i + 1], nodes[i + 2]를 비교하여 최소값 만큼 세 공장에서 구매를 한다.
6. 만약 nodes[i + 1]이 nodes[i + 2]보다 작거나 같다면, 먼저 세 공장에서 구매를 해준다.
7. 이후 남은 nodes[i], nodes[i + 1]를 비교하여 최소 개수만큼 두 공장에서 구매를 해준다.
8. 만약 nodes[i]에 남아있는 라면이 있다면 모두 구매해 준다.
9. 위 작업을 마치고 ans에 저장된 값을 출력해 준다.

 

참고 사항

nodes배열을 10만보다 2크게 해준 이유는 i + 1, i + 2 비교를 쉽게 하기 위함이다.

질문 게시판에 반례가 잘 정리되어 있어 해당 부분을 참고하면 문제를 접근하기 쉽다.

https://www.acmicpc.net/board/view/126171

 

반례 리스트

// 2부터 먼저 지워야 하는 케이스
4
1 2 1 1
// 정답 : 12
    
// 2부터 먼저 지워야 하는 케이스
4
2 4 2 2 
// 정답 : 24
    
// 2부터 먼저 지워야 하는 케이스
4
1 4 3 3 
// 정답 : 26
    
// 3부터 먼저 지워야 하는 케이스
4
1 3 3 1
// 정답 : 19
    
// 2, 3을 연속해서 지워야 하는 케이스
4
2 5 4 2
// 정답 : 31
    
// 여러 가지 숫자 케이스
7
2 3 2 3 3 2 1 
// 정답 : 38

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

int n, ans;
int nodes[10002];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> nodes[i];
	for (int i = 0; i < n; i++) {
		if (!nodes[i]) continue;
		if (nodes[i + 1] > nodes[i + 2]) {
			int common = min(nodes[i], nodes[i + 1] - nodes[i + 2]);
			ans += common * 5;
			nodes[i] -= common;
			nodes[i + 1] -= common;

			common = min({ nodes[i], nodes[i + 1], nodes[i + 2] });
			ans += common * 7;
			nodes[i] -= common;
			nodes[i + 1] -= common;
			nodes[i + 2] -= common;
		}
		else {
			int common = min({ nodes[i], nodes[i + 1], nodes[i + 2] });
			ans += common * 7;
			nodes[i] -= common;
			nodes[i + 1] -= common;
			nodes[i + 2] -= common;

			common = min(nodes[i], nodes[i + 1]);
			ans += common * 5;
			nodes[i] -= common;
			nodes[i + 1] -= common;
		}
		ans += nodes[i] * 3;
		nodes[i] = 0;
	}
	cout << ans;
}