이 문제를 통해 세그먼트 트리의 활용법을 제대로 이해해야 한다. 해당 쿼리의 연속합을 구하는 과정에서 부분 문제들의 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] ..

문제를 잘 보면 나눠줄 수 있는 "최대" 길이이므로 만족하는 숫자들의 범위 중 최댓값을 출력해주는 것이다. 따라서 이분탐색의 upper_bound를 활용해주면 된다. Upper_bound의 대략적인 skeleton code는 다음과 같다. // Upper_bound (이분탐색에서의 상계를 구하는 방법) int start = 0; int end = vector_container.size(); while (start M >> N; vector data_store; for(int i = 0; i > temp; data_store.push_back(temp); } sort(data_..

문제 자체는 그렇게 어렵지 않다. i번째에서 거리는 사실상 i-1번째의 상태에 의해서 결정되는 양상으로 진행된다. 추가적으로 조건을 잘 살펴보면 i분째 상태는 지침지수와 운동상태인지/쉬는 상태인지 여부에 따라 결정된다. 따라서 이러한 측면에서 3차원 DP가 필요하게 된다. dp[i][j][k] = i번째 분이 지났을 때 지침 지수가 j일때 달린 거리(단, k가 0이면 i번째 분일 때 쉰 상태, 1이면 달린 상태) 그리고 조건을 활용해서 점화식을 잘 세우면 다음과 같다. (단, d[i]는 i번째분에서 달릴 경우 갈 수 있는 거리) 1) 현재 움직히고 있는 상황인 경우(k가 1) dp[i][j][1] = dp[i - 1]j - 1][1] + d[i]가 기본적인 상황이다. 단, 만약 j가 1인 경우에는 dp[..

잘 생각해보면 10^6까지이므로 충분히 모두 다 조사해도 시간안에 무조건 들어온다. 다만, 중복되는 계산이 엄청나게 많을 것 처럼 보이므로 DP를 활용해서 중복되는 계산을 줄이는 것이 이 문제의 핵심이다. "dp[n] : 정수 N이 주어졌을 때 연산을 활용해서 1을 만들 수 있는 횟수의 최솟값" 이라 잡으면 점화식은 dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]이다. 다만, dp[1] = 0, dp[2] = 2; dp[3] = 4는 Base case이므로 따로 넣어준다. #include #include #include #include using namespace std; int dp[1000001]; int recursion(int n){ if(n == 1 || n == 2 ..