백준 (224) 썸네일형 리스트형 백준 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.. 백준 2056 - 작업 작업 간 선행관계가 제시되어 있으므로 작업들의 관계는 DAG가 되고 DP를 통해 각 작업을 끝내는데 필요한 최소시간을 찾아 더해주면 된다. 포레스트 형태에 대해 유의하여 구현한다. 전체 코드 더보기 #include using namespace std; using graph = vector; int finished[100001]; int fee[100001]; int memo[100001]; int dp(int node, graph &al); int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); int n; cin >> n; memset(memo, -1, sizeof memo); graph task(n + 1); for (int i = 0;.. 백준 1285 - 동전 뒤집기 www.acmicpc.net/problem/1285 $N \times N$으로 놓여진 동전을 한행씩, 한열씩 뒤집을 수 있을 때 T의 갯수를 최소화 하는 문제이다. 이 문제는 $2^N$ 완전탐색을 통한 전처리 후 나머지를 그리디하게 결정하는 방법으로 풀 수 있다. 각 행을 뒤집는 경우를 완전탐색으로 결정한다고 해보자. 각 행에 대해 뒤집을지 말지 결정하는 경우의 수를 $2^N$의 시간 복잡도로 찾을 수 있다. 각 행에 대해 뒤집는 연산이 끝나면 각 열에 대해 뒤집었을 때와 뒤집지 않을 때의 T의 개수를 비교하여 T가 더 적은 쪽을 선택해나가는 방식으로 답을 구할 수 있다. 행이 아니라 열을 뒤집는 경우에 수에 대해 탐색하고 각 행을 뒤집을지 결정해도 상관없다. 총 시간복잡도는 $O(2^NN^2)$ 가 된.. 이전 1 ··· 36 37 38 39 40 41 42 ··· 45 다음
