그리디 (1)

 

 

 

BOJ14501 퇴사

N일간 잡힌 각 상담의 기간과 금액이 주어질 때 N일동안 상담으로 벌 수 있는 금액의 최댓값을 찾는다.

냅색 문제 같은 건데 N≤15라 단순히 시작/종료 시간 기준으로 최대 금액을 계산해 N²로 해결하면 된다.

 

 

 

BOJ12904 A와 B

A와 B로만 이루어진 문자열 S와 T가 주어질 때 S를 T로 바꿀 수 있는지의 여부를 구한다.

문자열 뒤에 A를 추가하거나, 문자열을 뒤집고 B를 추가하는 연산만 할 수 있다.

문자가 추가되는 위치는 A,B 관계없이 문자열의 가장 끝이므로 S→T로 생각하지 말고 T→S로 생각한다.

 

 

 

BOJ8980 택배

N개의 마을과 마을 간 배송할 박스 정보 M개가 주어질 때

앞으로만 운행할 수 있고 용량이 C인 트럭으로 가장 많이 배송할 수 있는 박스 개수를 구한다.

각 마을에서 내려야 할 택배 박스의 개수를 저장하는 배열을 이용한다.

생각하기 어려웠다 ㅠ

	for (int cur = 1; cur <= N; cur++) {
		ANS += del[cur]; CAP -= del[cur]; //cur에 배달완료

		for (pair<int, int> b : box[cur]) {
			int nxt = b.first;
			int wei = b.second;
			int over = wei - (C - CAP);
			if (over <= 0) { CAP += wei, del[nxt] += wei; continue; }

			for (int far = N; far > nxt; far--) {
				if (del[far] >= over) {
					del[far] -= over; CAP -= over; over = 0; break;
					//far에 도착할 게 over보다 큼 => over만큼 빼고 over만큼 실음
				}
				else {
					over -= del[far]; CAP -= del[far]; del[far] = 0;
					//far에 도착할 게 over보다 작음 => 다 빼고 over되는 양 줄여줌
				}
			}
            
			wei -= over; CAP += wei; del[nxt] += wei;
		}
	}

 

 

 

BOJ1826 연료 채우기

트럭으로 가야할 마을까지의 거리 L과 현재 기름의 양 P가 주어질 때

마을에 도착할 수 있도록 N개의 주유소 중 멈춰야할 주유소 개수의 최솟값을 구한다.

현재 위치까지 오는 데 연료가 충분하면 멈추지 않고,

연료가 부족하면 PQ를 이용해 이전 주유소에서 주유할 수 있는 최댓값만큼 주유한다.

처음에 각 주유소마다 PQ를 만든 만행을 저질렀더니 당연히 시간초과였음

	for (int i = 1; i <= N + 1; ++i) {
		PQ.push(OIL[i - 1].second);

		P -= (OIL[i].first - pos); pos = OIL[i].first;
		while (P < 0  && !PQ.empty()) ANS++, P += PQ.top(), PQ.pop();
		if (P < 0) { printf("-1"); return 0; }
	}

 

 

 

BOJ13904 과제

마감기한까지 남은 일수 d와 점수 w가 주어진 N개의 과제를 수행해 얻을 수 있는 점수의 최댓값을 출력한다.

과제는 마감일이 빠른 순으로 정렬하고 PQ에 과제의 점수가 큰 순으로 마감일까지의 일수만큼 과제를 넣어놓는다.

가장 보편적인 그리디 문제인 듯

	for (int i = 0; i < N; ++i) {
		if (pq.size() < H[i].d) pq.push(H[i].w);
		else if(pq.size()==H[i].d){
			if (pq.top() < H[i].w) pq.pop(), pq.push(H[i].w);
		}
	}

 

 

 

BOJ14939 불끄기

이미 지나온 곳으로 다시 불을 끄러 가지 않아야 최소 횟수를 구할 수 있다.

따라서 왼쪽 위부터 오른쪽 아래 순으로 불을 끈다.

불이 켜져있고 아니고는 비트마스크로 해결

씽크빅 ㅜㅜ

 

 

 

 

어려웡

 

그리디는 뭔가 명확한 규칙이 없는 것 같아서..? 좀 생각하기 어렵다 ㅜ

대개 정렬을 이용하거나 뭐 최소/최대가 되기 위한 조건을 잘 생각해서 푸는 문제들인 것 같은데

좀 더 연습이 필요할 듯