전체 글 (346) 썸네일형 리스트형 [ICPC] 백준 5719 - 거의 최단 경로 http://icpc.me/5719 Step 1. 최단 경로를 구해보자. 다익스트라를 통해 어렵지 않게 구할 수 있다. 만약 경로를 못찾으면 거의 최단 경로라는 말 자체에 모순이 있는 것이므로 -1를 출력해주자. 노드 간 간선이 최대 하나 존재할 수 있다는 설명과 후술할 step 2를 고려하여 인접행렬로 그래프를 구성하여 구성하자. 다익스트라를 통해 구한 시작점부터 각 정점까지의 길이는 따로 저장할 수 있도록 하자. Step 2. 도착점부터 시작점까지 bfs를 통해 거슬러 올라가도록 한다. 올라가는 과정에서 도착점까지의 길이 = 정점 i까지의 길이 + 정점 i와 도착점에 연결된 간선의 길이 를 만족한다면 그 간선은 최단 경로에 포함되는 간선이 된다. 해당 간선으로는 통행할 수 없도록 하자. 또한 최단 경.. 백준 14247 - 나무 자르기 http://icpc.me/14247 날이 지나면서 가장 크게 자라는 나무를 가장 늦게 잘라야 최대한 많은 나무를 얻을 수 있다. 나무가 자라는 양을 기준으로 정렬 후 날짜별로 수확할 수 있는 나무의 양을 계산하면 된다. 전체코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include using namespace std; using pii = pair; using ll = long long; ll res; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector tree(n); for (auto &x : tree) c.. 백준 16456 - 하와와 대학생쨩 하와이로 가는 거시와요~ icpc.me/16456 몇가지 항에 대해 직접 손으로 경우의 수를 찾아보면 $f(n) = f(n - 1) + f(n - 3)$ 형태의 점화식이 성립됨을 찾을 수 있다. DP를 통해 이 점화식을 풀자. 전체코드 더보기 #include #define mod 1000000009 using namespace std; using ll = long long; ll dp[50000]; int main() { int n; cin >> n; dp[0] = dp[1] = 1; dp[2] = 2; for (int i = 3; i < n; ++i) dp[i] = (dp[i - 1] + dp[i - 3]) % mod; cout [KOI] 백준 10165 - 버스 노선 www.acmicpc.net/problem/10165 한 노선에 완전히 포함되는 노선은 제외하므로 솔루션은 구간을 검사하는 스위핑에 근간을 두고 있다. 버스 정류장이 원형으로 연결되어 있으므로 각 케이스에 대한 전략과 그 구현이 복잡해진다. Step 1. 문제 접근을 용이하게 하기 위해 각 버스 노선을 두 종류로 분리해보자. 1. 0 을 중간점으로 경유하지 않는 노선 line 2. 0 을 중간점으로 경유하는 노선 circle 1번의 경우 버스 노선이 직선으로 생겼다고 취급해도 된다. 2번의 경우 버스 노선이 N - 1이하의 시작점에서 0번 정류소를 지나가는 형태이다. Step 2. 이 두 종류의 노선에서 3가지의 경우의 수를 통해 어떤 것을 구해야 하는지 파악해보자. 1. line과 line의 비교 li.. 백준 15681 - 트리와 쿼리 주어진 입력으로 트리를 구성한다. 그리고 그래프 탐색을 통해 해당 노드의 깊이도 저장하도록 한다. 그 후 탑다운 DP를 통해 해당 노드가 가지는 자식의 갯수를 계산하여 출력하도록 하면 된다. 전체 코드 더보기 #include using namespace std; vector al[100001]; int depth[100001]; int dp[100001]; int build_tree(int v); int main() { memset(dp, -1, sizeof dp); ios::sync_with_stdio(false); cin.tie(0); int v, rt, qry; cin >> v >> rt >> qry; for (int i = 0; i > g.. 이전 1 ··· 60 61 62 63 64 65 66 ··· 70 다음
