https://www.acmicpc.net/problem/2001 2001번: 보석 줍기 첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 www.acmicpc.net visited[1 > k; for (int i = 0; i > input; gold_check[input] = i; } for (int i = 0; i > a >> b >> c; adj[a].push_back(make_pair(c, b)); adj[b].push_bac..

www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1≤N≤100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득을 www.acmicpc.net 현재 위치에서 최댓값을 구할 때, 그 전 위치(i-1)에서 보석 줍기가 끝나는 최댓값 + 현재 보석(gold[i]) 과 현재 위치에서 끝나는 m개의 보석줍기(psum[i] - psum[i-m]) 중 값이 더 큰 것이 현재 위치에서 보석 줍기가 끝날 때 최댓값이다. 코드 #include #include #include using namespace std; int n, m; vector psum(100001)..