(백준 15748번 Rest stops C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 8탄

애증의 그리디 8탄! 영어로 되어 있어서 쫄리지만 내용은 생각보다 간단한 문제 Rest stops를 풀어보았다.

 

이전 포스팅은 여기에!↓

2024.01.06 - [알고리즘] - (백준 2217번 로프 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 7탄

(백준 2217번 로프 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 7

백준 15748번

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

15748번: Rest Stops

 

풀이 과정

한마디로 존버 전략이라고 할 수 있다.

 

보상이 제일 큰 곳에서 Farmer가 올 때까지 쭉 기다리다가 다시 두번째로 보상이 큰 곳으로 가서 Farmer를 기다리는 방식으로 행동하면 된다.

 

상당히 단순한 로직! 인데... 자꾸 틀렸다고 해서 너무 슬펐다..🥶🥶

알고보니 자료형 문제였는데...!!

 

보통은 입력값의 자료형에 신경을 많이 쓰는데, 이번에는 나올 수 있는 정답의 자료형이 int로 커버할 수 있는 범위를 넘기 때문에(int는 대략  $\pm2*10^9$ 정도를 커버한다) int의 범위를 넘을 수 있을거 같으면 long long 이라는 자료형을 사용해야 한다. (라이님 블로그 보고 알았따..) 

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220775134486&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

탐욕적 기법(Greedy Algorithm) (수정: 2019-11-23)

알려주셔서 정말정말 감ㅅㅏ합니다ㅠㅠㅠ

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>


int main() {
	int L, N, rF, rB, temp1, temp2;
	scanf("%d %d %d %d", &L, &N, &rF, &rB);
	std::vector<std::pair<int, int>> v;
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &temp1, &temp2);
		v.push_back(std::make_pair(temp2, temp1));
	}

	std::sort(v.rbegin(), v.rend());

	long long max_t = 0; // max_tastiness 
	long long before = 0, after = 0; // location will be moved from 'before' to 'after'.
	// before과 after의 형이 int이면 틀리게 된다. 
	// 대신 max_t += (long long)((after - before)* (long long)(rF - rB))* (long long)v[i].first; 이라고 명시하면 가능!
	// (long long)((after - before)* (rF - rB))* (long long)v[i].first; 이건 틀리게 된다.
	for (int i = 0; i < N; i++) {
		if (after >= v[i].second) continue;
		after = v[i].second; 
		max_t +=((after - before)* (rF - rB))* v[i].first;
		before = after;
	}

	printf("%lld", max_t);
	return 0;
}