Approach 사실 예제 입력 2에 대한 설명을 보고 가장 큰 아이디어를 얻었다. 문제에서 1번으로 가는 길은 유일하다는 표현을 통해 사이클이 없는 트리 구조임을 쉽게 파악할 수 있다. 따라서 점들의 관계를 표시해보면, 일종의 1번 노드를 루트 노트로 하는 트리로 이해할 수 있다. 그런데, 자식 노드를 기준으로 점차적으로 위로 올라오면서 양이 들어오는 양상이다. 추가적으로 해당 점이 양이 있는 곳이라면 자식에서 올라오는 양의 수에 해당 점에 있는 양의 수를 더해주면 되고, 반대로 늑대가 있는 점이라면 자식에서 올라오는 양의 수에 해당 점에 있는 늑대의 수를 뺴주면 된다. (만약 음수가 나올 경우에는 0으로 만들어주면 된다.) 늑대는 이동하지 않는 상황이므로 dfs를 돌면서 양의 값을 ret으로 잡으면 ..

Moo(n)를 구성하는 것은 Moo(n-1)에 의해 결정된다는 것을 활용해서 분할 정복 아이디어가 떠올랐으면 충분하다. 다만, 이 문제에서 해당 자릿수를 만족하는 알파벳을 구하는 것이 핵심이므로 바로 분할정복으로 들어가지말고, Moo(n)에 해당하는 자릿수를 구해서 어느 Moo value 자리에 의해 알파벳이 결정되는지 판단해주면 된다. Moo(n)은 Moo(n- 1) + M + o * (n + 2) + Moo(n - 1)이므로 해당 자릿수가 앞의 Moo(n - 1) 위치인지, 가운데인지, 뒤의 Moo(n - 1) 위치에 있는지 판단해주면 된다. 만약 앞 뒤의 Moo(n - 1)에 존재하는 경우, 분할정복으로 처리해주면 되고 가운데에 있는 경우는 맨 처음 자리만 빼고는 o을 출력해주면 된다. 다만, Ba..

백준 14601번 샤워실 바닥 깔기 문제와 비슷한 느낌으로 처리하면 된다. viyoung.tistory.com/146 [백준 14601번] [분할 정복] 샤워실 바닥 깔기 (Large) 분할정복의 대표적인 예시인 L-트로미노 타일링 문제이다. (사실 그냥 풀라고 했으면 못풀었을 듯) 접근 방법은 다음과 같다. (자세한 내용은 wogud6792.tistory.com/64 참고) 1. 전체 타일을 4등분해서 viyoung.tistory.com 위의 문제와 14601번 문제의 공통점은 4개의 영역으로 나눠서 분할정복 한 뒤, 각각의 정보를 통해 전체 영역의 정보를 처리하는 것이다. 이 문제의 경우 안에 있는 element결과를 이용해서 바깥 부분에 괄호를 감싸야하므로 (좌상단정보 + 우상단 정보 + 좌하단정보..

생각해보면 쉬운데, 분할정복이 아직 익숙하지 않아 쉽게 발견을 못했다. 항상 모든 문제를 풀 때, 큰 문제를 작은 문제로 나눠서 풀 생각부터 진행해야 한다. 즉, 이 문제를 분할 정복 문제로 느끼기 위해서는 근본적으로 제일 큰 덩어리와 나머지 묶음들을 움직이는 것으로 이해했어야 한다. 그러면 분할 정복 문제로 파악할 수 있다. Divide and conquer하는 느낌을 잘 받아두도록 하자. 쪼개고 합해서 처리하고, 가장 작은 component는 직접 처리하는 양상을 이해해야 한다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; vector r..

백준 16993번과 매우 유사하다. 다만 차이점이 2개 존재한다. 백준 16993번의 경우에는 단순한 금광 세그라면, 이 문제의 경우에는 U와 V를 곱해주는 과정을 수반하게 된다. 추가적으로 이 문제에서는 세그 트리를 중간에 수정함으로써 update과정을 진행해주어야 한다. 일단 처음에 고전했던 부분은 U와 V를 곱해주는 과정을 어떻게 처리할 것인지에 대한 아이디어이다. U의 경우에는 16993번에서 한 결과값에 U만 곱해주면 되는데 V의 경우가 처리하기가 처음에 껄끄러웠다. j - i를 처리해주어야 하기에 처음에는 왼쪽을 기준으로 연산했을 때와 오른쪽을 기준으로 연산했을 때의 갯수를 구조체 안에 넣을 생각을 먼저 했는데 너무 비효율적인 것 같아서 포기하였다. 사실 고민을 좀 해보면, V를 처음 init..

이 문제를 통해 세그먼트 트리의 활용법을 제대로 이해해야 한다. 해당 쿼리의 연속합을 구하는 과정에서 부분 문제들의 partition울 활용할 수 있을 것 같다는 느낌이 직관적으로 매우 강하게 든다. 이 지점에서 Segment Tree 기법을 생각했어야 한다. Segment tree를 처음 init시키는 과정에서 저장한 정보를 활용하여, 주어진 쿼리의 연속합을 도출할 수 있을 것 같은 느낌이 들면 된다. 다만, 문제가 연속합을 도출하기 위해서는 분할정복의 느낌으로 오른쪽과 왼쪽 결과값을 활용해서 도출해주어야하는데 이 과정에서 필요한 정보가 왼쪽을 기준으로 진행했을때의 최대 연속합과 오른쪽으로 진행했을 때의 최대 연속합이다. 또한, 추가적으로 이 모두를 고려했을 때의 최대 연속합이 필요하다. 요약하자면 다..

분할정복의 대표적인 예시인 L-트로미노 타일링 문제이다. (사실 그냥 풀라고 했으면 못풀었을 듯) 접근 방법은 다음과 같다. (자세한 내용은 wogud6792.tistory.com/64 참고) 1. 전체 타일을 4등분해서 하수구의 위치를 찾는다. 2. 하수구가 없는 영역들은 가안 안쪽 타일을 색칠한다. 3. 나눠진 각 타일을 기준으로 1,2 과정을 반복한다.(다만, 색칠된 타일은 하수구와 동일하게 취급해서 진행해주면 된다.) 그리고 가장 작은 단위인 2 x 2가 나올 때 직접 처리를 해주면 된다. #include #include #include #include #include #include using namespace std; int check_count = 1; int dp[129][129]; int..

문제 자체는 대표적인 분할정복 예제 중 하나인 거듭수에 대한 계산이다. 그런데 피보나치를 저렇게 나타낼 수 있는 것에 대해서 되게 신기했다. n어 엄청나게 커도 게속해서 절반 쳐주면서 계산하면 O(lgn)으로 처리할 수 있다. #include #include #include #include #include typedef long long ll; using namespace std; void fib_set(int n, vector &dp){ if(n == 1) { dp[0] = 1; dp[1] = 1; dp[2] = 1; return; } if(n % 2 == 0){ vector data(4, 0); fib_set(n / 2, data); dp[0] = (data[0] * data[0] + data[1] ..