Stargazer

#include #include using namespace std; int n, k; // n: 물품의 수, k: 버틸 수 있는 무게 int DP[101][100001]; int W[101]; int V[101]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k; for (int i = 1; i > W[i] >> V[i]; } for (int i = 1; i

접근 3가지의 선택: -1, +1, x2 그리고 가장 작은 weight를 가지는 길을 찾아야 한다. 그래서 일단은 너비 우선 탐색을 선택했다. 왜냐하면 가장 짧은 길을 탐색하기 위해서 너비를 우선으로 탐색해야 하기 때문이다. 그렇게 하기 위해 큐를 이용하기로 했다. 그리고 가중치가 0,1 로 다르기 때문에 다익스트라 알고리즘을 이용하기로 했다. 전략 큐에 n의 위치를 넣고, 3가지 선택 중에 선택을 할 수 있는 조건을 만족하면(범위 내 이고, 가중치가 더 작으면) 선택을 하여 큐에 삽입을 한다. 이때, 중요한 건 선택 순서가 중요한데, 2배를 하면 가중치가 0이기 때문에, 3가지 중에 2배를 하는 것을 먼저 선택하도록 순서를 정해야, 최소의 가중치를 구할 수 있다. 방향성이 음수로 가는 방향은 -1 밖에..