[C++] 백준 1446 지름길

#include <iostream>
#include <string.h>
#include <vector>
#include <map>
 
int DP[10001] = { 10000 };
 
int main()
{
	int N = 0;
	int D = 0;
	std::cin >> N >> D;
 
	std::vector<std::vector<std::pair<int, int>>> vec(10001, std::vector<std::pair<int, int>>());
 
	for (int i = 0; i < N; ++i)
	{
		int iX = 0;
		int iY = 0;
		int iNumber = 0;
		std::cin >> iX >> iNumber >> iY;
 
		if (iNumber > D)
			continue;
 
		if (iNumber - iX < iY)
			continue;
 
		vec[iNumber].push_back({ iX,iY });
	}
 
	DP[0] = 0;
 
	for (int i = 1; i <= D; ++i) 
	{
		DP[i] = DP[i - 1] + 1;
 
		if (!vec[i].empty())
		{
			for (int j = 0; j < vec[i].size(); ++j)
			{
				DP[i] = std::min(DP[i], DP[vec[i][j].first] + vec[i][j].second);
			}
		}
	}
 
	std::cout << DP[D];
 
	return 0;
}

계산하면서 가는 걸로

1. 출발지에서 그 다음만큼의 크기를 확인