[BOJ] C++ 그리디 알고리즘 문제풀이 (1)

🧨 백준 11047번

문제 출처 : 백준 11047번

문제 난이도 : 실버1

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

11047번: 동전 0

🧨 알고리즘 선택 및 C++ 코드

동전문제야말로 대표적인 그리디 알고리즘이다. 가장 큰 동전단위부터 내림차순으로 내가 원하는 금액 K를 채워나가면 된다. 마치 stable sorting과 비슷한 느낌이랄까.. (x, y 순으로 정렬하려면 y먼저 정렬하고 x 기준으로 정렬하는 것처럼) 

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

int main(void) {
	int n, k;
	scanf("%d %d", &n, &k);

	vector<int> coin(n);
	int target = 0;

	for (int i = 0; i < n; i++) {
		scanf("%d", &coin[i]);
	}

	for (int i = n; i > 0; i--) {
		target += k / coin[i - 1];
		k = k % coin[i - 1];
	}

	printf("%d", target);

	return 0;
}

---

🧨 백준 4796번

문제 출처 : 백준 4796번

문제 난이도 : 실버5

문제 링크 : www.acmicpc.net/problem/4796

4796번: 캠핑

🧨 알고리즘 선택 및 C++ 코드

L < P < V 만 생각하고 풀다가 나머지와 L 크기에 따라 마지막에 더해주는 일 수가 달라질 수도 있음을 깨달았다. 대표적인 그리디 알고리즘 문제였고, 나눗셈 연산을 잘 이용하면 되었다. 간결한 코드를 위해 삼항연산자 ? : 를 오랜만에 써봤다. 가독성은 떨어지지만 간결해서 좋다.

#include <iostream>
using namespace std;

int main(void) {
	int limit, period, vacation;
	int target = 0;
	int count = 1;

	while (1) {
		scanf("%d %d %d", &limit, &period, &vacation);

		if (!limit && !period && !vacation)
			break;
		target = (vacation / period) * limit;
		target += (vacation % period) > limit ? limit : (vacation % period);
		printf("Case %d: %d\n", count, target);
		count++;
	}

	return 0;
}

---

🧨 백준 16435번

문제 출처 : 백준 16435번

문제 난이도 : 실버5

문제 링크 : www.acmicpc.net/problem/16435

16435번: 스네이크버드

🧨 알고리즘 선택 및 C++ 코드

스네이크버드.. 뱀과 새를 닮았는데 어떻게 귀엽다고 할 수 있지..

스네이크버드의 처음 길이가 L일 때 과일들을 먹어 늘릴 수 있는 최대 길이를 구해야 하므로 과일을 정렬하는 작업이 필요하다. 과일을 정렬하여 내가 먹을 수 있는 범위는 모두 먹는 방법이다. 이때 정렬은 c++ 자체 sort 함수(nlogn의 시간복잡도를 가지는)를 사용하면 문제없다. 정렬해야 한다는 생각이 핵심이었고, 그 외에는 그리디 알고리즘으로 그냥 계속 먹으면 된다.이쯤 되면 그리디 알고리즘은 정해진 구현 방식은 없지만 if 조건문을 기준으로 어떤 처리를 해 줄 것인가 말 것인가로 나눌 수 있을 것 같다. 또는 나눗셈 연산(몫과 나머지)을 열심히 하면 되는 거 같다.

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

int main(void) {
	int N, L;
	scanf("%d %d", &N, &L);
	vector<int> fruit(N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &fruit[i]);
	}

	sort(begin(fruit), end(fruit));

	for (auto f : fruit) {
		if (f <= L) {
			L++;
		}
	}

	printf("%d", L);

	return 0;
}

---

🧨 백준 13305번

문제 출처 : 백준 13305번

문제 난이도 : 실버4 (하지만 위의 3문제보다 어려웠다)

문제 링크 : www.acmicpc.net/problem/13305

13305번: 주유소

🧨 알고리즘 선택 및 C++ 코드

그리디 알고리즘을 이용해 푸는 거라는데 생각보다 접근하기 어려웠다.

1) 머리속으로 어떻게 풀어야 할지 감은 오는데 구현하기 애매했다. 첫번째로 시도한 로직은, 현재 내가 있는 도시를 기준으로 앞으로 가야할 도시들의 주유소 가격을 미리 체크해서 지금 기름을 얼마나 넣을지를 결정하는 방식이었다. 이중 루프를 사용해야했기 때문에 상당히 비효율적이었고 이상하게 length_error도 많이 났다 (아마 이때 벡터 안 쓰고 어레이로 썼다면 해결되었을 수도 있다) 두번째로 시도한 방법은, 내가 가장 최근에 기름을 넣은 곳(min: 기름값이 쌌기 때문에 기름을 넣었을 것)을 min으로 두고 현재 도시의 기름값과 비교하는 것이다. min을 계속 갱신하며, 코드 상으로는 매번 바로 다음 도시까지의 거리만큼만 기름을 넣는 방식이지만 사실상 (min 가격) * (바로 다음 도시까지의 거리) 이므로 첫번째 시도한 방법과 같은 그리디 알고리즘이다.

2) 예제 입출력은 모두 맞게 나왔는데 제출해보니 런타임에러 대환장 파티였다. OutofBounds, LengthError가 계속 뜨길래 굉장히 난감했다. 구글링한 예제들 보니까 대부분 vector를 안 쓰고 array를 썼길래 나도 벡터 버리고 어레이로 갈아탔다. 결과적으로 어레이로 갈아타니까 간단히 해결됐는데, 앞으로도 벡터의 begin(), end(), push_back 등의 내장함수를 쓸 일이 아니라면 그냥 어레이를 써야겠다. 몇번의 제출 끝에 성공해서 다행이다. (최근 풀었던 백준 문제 중에 오류 해결에 제일 오랜 시간을 쓴 문제가 아닌가 싶다)

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    int N;
    long long link[100001];
    long long node[100001];
    
    scanf("%d", &N);
    
    for(int i = 0; i < N - 1; i++) {
        cin >> link[i];
    }
    for(int i = 0; i < N; i++) {
        cin >> node[i];
    }
    
    long long target = 0;
    long long min = node[0];
    for(int i = 0; i < N - 1; i++) {
        if(node[i] < min) {
            min = node[i];
        }
        target += link[i] * min;
        
    }
    
    cout << target;

    return 0;
}

---

그리디 관련 문제 몇 개 더 풀어봐야 감이 올 거 같다.