[백준 26267] 은?행 털!자 1 (C++)

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

문제

---

프로 은행강도 시우가 은행을 털려고 한다. 시우가 달려가는 일직선 경로 위엔 N개의 은행이 있다. i번째 은행은 직선상에서 서로 다른 좌표 X_i에 위치하며, 시간이 정확히 T_i 일 때만 문이 열려 입장할 수 있다. 또한 이 은행을 털면 C_i원을 얻을 수 있다.

시우는 직선 상에서 임의의 정수 좌표에서 시작해 움직인다. 움직이는 동안 좌표는 증가해야 한다 (멈춰 설 수 없음에 주의하라). 시간은 0으로 시작하며 좌표가 1만큼 증가할 때 시간도 1만큼 증가한다.

시우는 문이 열려 있는 은행을 마주치면 반드시 털고 가며, 매우 숙련돼있기 때문에 은행을 털어도 시간이 전혀 증가하지 않는다.

시우가 적절한 위치에서 시작했을 때, 얻을 수 있는 최대 금액을 출력하여라.

 

입력

---

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 300000)

두 번째 줄부터 N개의 줄에 걸쳐 각 줄마다 i와 X_i가 증가하는 순서대로 정수 X_i,T_i,C_i가 주어진다. (0 ≤ X_i,T_i,C_i ≤ 10⁹)

모든 X_i는 서로 다르다.

 

출력

---

시우가 얻을 수 있는 최대 금액을 출력한다.

 

문제 풀이

---

자료구조 문제.

 

T_i에만 문이 열리므로 위치에 상관 없이 특정 한 위치를 선택하면 T_i - X_i만큼 차이나는 모든 은행들만을 털 수 있다. 따라서 <T_i - X_i, 은행을 털었을 때 얻는 금액>을 저장하는 map을 만들어 해당 자료구조에 저장해두면 된다. T_i - X_i를 key로 사용하여 find()를 통해 해당 키가 존재하는지 확인한다. 없다면 해당 key를 바탕으로 값을 저장해두고, 존재한다면 은행을 털어서 얻는 금을 value에 추가해두면 된다.

 

아래는 코드.

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

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

	map<int, long long> m;
	int N;
	int X, T, C;
	map<int, long long>::iterator it;
	long long answer = 0;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> X >> T >> C;
		it = m.find(T - X);
		if (it == m.end())
		{
			m.insert({T-X, C});
			answer = max(answer, (long long) C);
		}
		else
		{
			it->second += C;
			answer = max(answer, it->second);
		}
	}
	cout << answer << "\n";
	return 0;
}