본문 바로가기

PS87

백준 2873 / C++ https://www.acmicpc.net/problem/2873 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net [ 풀이 ] 홀수인 변이 있다면 전부 방문할 수 있음은 자명하다. 모두 짝수인 경우의 문제를 풀자. 규칙을 찾아보자. 전부 방문하는건 불가능하다. 증명은 다음과 같다. 전부 방문하려면 (r-1)(c-1)개의 화살표가 필요하다. 이 값은 홀수이다. 그런데 시작점에서 끝점으로 가는데엔 짝수번의 화살표가 필요하다. 따라서 홀짝성에 위배된다. 그럼 되도록 1개만 제외하고 방문하고 싶다. 이런 문제의 .. 2022. 8. 12.
플로우 - Dinic, Edmonds-Karp 알고리즘 1. [ Dinic ] const int MAX = 808; vectorg[MAX]; int work[MAX], lv[MAX], cap[MAX][MAX], flow[MAX][MAX]; struct Dinic { void add(int u, int v, int c) { g[u].push_back(v); g[v].push_back(u); cap[u][v] += c; } bool bfs(int S, int T) { memset(lv, -1, sizeof(lv)); queueq; lv[S] = 0; q.push(S); while (q.size()) { int cur = q.front(); q.pop(); for (int nxt : g[cur]) { if (lv[nxt] == -1 && cap[cur][nxt] .. 2022. 8. 8.
백준 21761 / C++ https://www.acmicpc.net/problem/21761 21761번: 초직사각형 1차원 공간에서의 선분, 2차원 공간에서의 직사각형, 3차원 공간에서의 직육면체를 생각해 보자. 선분의 크기는 변수 $A$로, 직사각형의 크기는 두 개의 변수 $A$와 $B$로, 직육면체의 크기는 세 개 www.acmicpc.net [ 풀이 ] 부피 ABCD에서 한 변을 증가시키면 (A+U)BCD가 된다. 그럼 매번 변화시키면서 1+U/A가 커지도록 해주면 된다. 그리디하게 매번 A,B,C,D중 제일 큰 U를 뽑아서 1+U/x가 제일 큰걸 매번 뽑아주면 된다. 기존 ABCD에서 이렇게 가장 큰 비율을 매번 곱해줘야 최대가 되는건 자명하다. 그 비율이 1보다 크기 때문에 항상 값이 커지기 때문이다. 매번 제일 큰 .. 2022. 8. 8.
백준 1234 / C++ https://www.acmicpc.net/problem/1234 1234번: 크리스마스 트리 첫째 줄에 트리의 크기 N, 빨강의 개수, 초록의 개수, 파랑의 개수가 주어진다. N은 10보다 작거나 같다. 빨강, 초록, 파랑의 개수는 0보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net [ 풀이 ] dp[h][r][g][b]를 h높이를 채울 것이고 지금까지 r, g,b만큼 색상을 쓴 경우의 수라고 하자. 상태전이는 다음과 같다. 1. 한 색으로 h칸을 모두 칠한다. : dp[h+1][r+h][g][b] 로 전이 (g, b도 마찬가지) 2. h가 짝수면 두개를 골라 절반씩 칠한다. : dp[h+1][r+h/2][g+h/2][b] * h!/(h/2)!(h/2)! 로 전이 (g, b도 마.. 2022. 8. 8.

티스토리툴바