대략적으로 그래프를 타고 넘어가면서 전파하는 양상이라는 것을 문제를 읽어보면 쉽게 판단할 수 있다. 처음에 생각한 방법은 DFS인데, 중간에 문제점이 있다는 것을 파악하고 포기하였다. 예를들어 DFS를 타고 넘어가면서 8분 정도에 특정 노드에 전파할 때 절반을 넘었다고 가정해보자. 단순하게 8분을 전파시점으로 생각하기 쉬우나, 이렇게 단순하게 접근하면 안된다. 예를 들어 다른 간선에서는 4분에 해당 노드에 접근을 시도했을 수도 있기 때문이다. 즉, 해당 간선을 기준으로 만족한다고 하여 그것이 가장 짧은 시간임을 보장할 수가 없게 된다. 따라서 이 부분에서 BFS를 강구한 것이다. 즉, 같은 시간에 전파되는 것들을 모두 다 처리하고 넘어가야 해당 노드에 전파되는 시점의 대소비교가 가능해진다. 귀찮아서 BF..

간단한 DFS문제이다. 사실 생각해보면 M을 기준으로 사이클 돌때를 판단해주면 된다. 주의해야할 지점은 바라보는 지점과 처리해야 하는 지점이 다르다는 것이다. 반복여부를 판단하기 위해서는 시작지점을 봐야하고, 문제에서 필요로하는 데이터는 1사이클의 마지막 데이터이기 때문이다. 다만, 일반적으로는 끝나는 데이터가 다시 시작지점이 되므로 이 부분을 핸들링해주면 되지만, 만약 1이 끝나는 지점의 경우는 예외 케이스가 발생할 수 있으므로 따로 처리해주면 된다. 추가적으로 가장 골치 아픈 지점이 다시 1로 돌아오는 것이 아니라 다른 지점으로 사이클을 형성하는 것이다. 이 부분을 해결하기 위해서 여러가지 방법이 있을 수 있다. pair 자료구조 등을 활용해서 처리할 수 있고 여러가지 방법이 존재한다. 따로 뺴서 계..

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

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

문제 상황을 이해하려고 끄적거리다보면 숫자를 키워나가면서, 자기보다 앞에 있는 숫자들은 무시한채 채워지지 않은 공간의 갯수를 세면서 자리를 파악하는 것이 핵심이다. 즉, k를 채우기 위해서 1~N까지의 자리 중 1 ~ k - 1번째 숫자가 위치한 곳을 제외하고 앞에서부터 남는 자리의 갯수를 input값이랑 비교해주면 된다. 이 방법으로 문제를 풀려면 다음과 같은 조건이 필요하다. 1. 몇번째 index까지 고려했을 때 주어진 숫자를 만족할 수 있는지 2. 숫자를 채우고나서 위상의 변경을 빠르게 반영할 수 있는지 이 중 2번째 조건에서 세그먼트 트리의 change 함수에서의 역할과 비슷함을 느끼고, 세그먼트 트리로 접근방법을 잡았다. 또한, 몇번째 index까지 고려해야하는지를 생각해야하므로 부분합 구조와..

전형적인 Segment tree 문제이다. 관련한 개녕은 www.crocus.co.kr/648 에 잘 나와있으므로 참고하도록 하자. Init, sum, update함수를 적당히 잘 구현해서 풀어주면 되는 문제이다. 중간중간에 숫자를 수정하고 구간 합을 구하는 지점에서 세그먼트 트리 문제임을 눈치챘어야 한다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); typedef long long ll; using namespace std; ll arr[1000000]; ll tree[1000000 * 4]; ll init(ll start, ll end, ll node){ if(start == end) return tree..

분할정복의 대표적인 예시인 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] ..