돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/8189 문제 풀이 일단 문제를 보면 몇 가지 사실들을 알 수 있다. 첫 번째로 답이 가능한 길이는 짝수이다. 좀 더 생각해보면 답이 가능할 조건을 다른 방법으로도 판단할 수 있다고 생각할 수 있다. 예를 들면 반으로 접었을 때 만나는 두 원소의 합이 모두 1일 때 Antisymmetry이다. 중요한 것은 1010101010... 과 같은 경우에 답의 스케일이 $O(N^2)$이기 때문에, 답의 개수를 하나하나 구하는 것은 불가능하다고 판단할 수 있으며, 따라서 (어떠한 조건의 ) 문제에서 구하고자 하는 구간의 개수를 한번에 구함으로서 문제를 해결하는 쪽으로 방향을 잡을 수 있다. 보통 구간과 같은 경우에는 동일한 시작점 혹은 끝점으로..

문제 링크 : https://www.acmicpc.net/problem/19265 문제 풀이 이 문제는 배열 p에 존재한 모든 $p_i$에 대해서 $T_i = Tp_i $ 인지를 S의 모든 구간에 T에 대해서 확인하는 문제이다. 여기서 어떤 형태를 비교하는 거니까 문자열 매칭과 비슷한 느낌을 받을 수 있다. 먼저 생각난 것은 KMP 였지만 KMP로는 풀 수 없는 형태였다. 실패함수가 좋은 형태로 나타나지 않기 때문에 KMP는 포기할 수 밖에 없었다. 이 상태에서 문제를 푸는 사고의 흐름이었다면 라빈-카프 해싱을 생각을 했어야 했다. $T_i = Tp_i $ 라는 것은 i 기반 해싱값과 pi 기반 해싱값이 같다는 거고, 좀 만 더 생각하고 식을 변형 시켜 보면 $\sum_{i}^{} i\times T_i ..

문제 링크 : https://www.acmicpc.net/problem/8103 문제 풀이 가능한 위치가 직사각형으로 주어진다. 직사각형이기 때문에 y 좌표가 가능한 범위는 x 좌표에 영향을 받지 않는다. 따라서 x와 y를 따로 놓고 생각해서 구할 수 있다. 주어진 문제를 축 별로 쪼개서 본다고 하면, 구간이 n개 주어지고 n개의 구간에서 각각 수를 하나 씩 뽑아야 하는데 이 수가 1~n까지 서로 다른 수여야 한다. 위의 문제를 어떻게 풀 수 있을까? 이미 1~i-1 까지 배정을 했다고 하자. 이제 i를 어떤 구간에다가 배정해야 할 지 골라야 한다. 가능한 구간은 s~e에서 s가 i보다 작으며, e가 i보다 큰 구간들이다. 이러한 구간들에서 e가 가장 작은 구간을 뽑는 것이 이득이다. 앞으로 가능한 구간..

문제 링크 : https://www.acmicpc.net/problem/10169 문제 풀이 부분 부분 알고 있었던 내용이었다. 간선이 하나씩 없어지는데 각각의 경우에 MST 길이 합을 구하는 문제이다. 가장 먼저 생각할 수 있는 부분은 맨 처음에 전체 그래프에서 MST를 구해서 MST에 쓰이는 간선과 쓰이지 않는 간선을 나눌 수 있다는 것이다. 또한 거기에 더해서 첫 MST 에 쓰이지 않는 간선들은 제외를 해도 길이 합이 변하지 않는 다는 것 까지 알 수 있다. 그렇다면 첫 MST에 쓰인 간선이 지워졌을 때 대체하는 최소 비용의 간선을 모든 간선에 대해서 다 구해야 한다. 그 이후로는 이 문제의 경험이 굉장히 도움이 되었다. MST에 속하지 않은 간선 들은 cross edge 또는 back edge가 ..

문제 링크 : https://www.acmicpc.net/problem/3682 문제 풀이 최소 간선을 추가해서 전체를 하나의 SCC로 만드는 문제이다. 먼저 주어진 그래프를 생각해보자. 애초에 문제에서 하나의 SCC 로 만드는 것이 목표이기 때문에 그래프를 SCC 간의 위상정렬로 놓고 생각하지 않을 이유가 없다. 따라서 그래프에서 먼저 SCC를 구하자. SCC 내에서는 서로 동치이기 때문에 추가적인 간선을 이을 필요가 없다. 따라서 처음에 구한 하나의 SCC 는 하나의 정점으로 대체하여 생각할 수 있다. 그렇게 변형된 그래프를 생각해보자. 그래프에는 사이클이 존재하지 않는다. 여기서 모든 정점을 묶어서 SCC로 만들어 주어야 한다. 이를 위해서는 모든 정점의 outdegree와 indegree가 1 이..

문제 링크 : https://www.acmicpc.net/problem/7117 문제 풀이 1 직접 푼 풀이이다. 나올 수 있는 모든 숫자의 종류는 대략 3^20 이다. 이는 3486784401 으로 10^9 보다도 크기 때문에 모든 숫자에 대해서 다 해보는 것은 옳지 못하다. 딱 문제와 같은 경우에 쓸 수 있는 방식이 Meet in the Middle 방식이다. 10자리씩 끊어서 생각을 하자. 10자리 수에 대해서 각각 mod n 값을 계산해서 저장해 두자. 특히 n의 제한이 500000이기 때문에 그냥 각 나머지에 대해서 그 나머지를 가지는 최솟값을 저장해 둘 수 있다. 이후 10자리 수에 대해서 10^10을 곱한 후에 mod n 을 취한 값이 x 라고 하자. 첫 10자리는 그대로 쓰고 뒷 열자리는 ..

문제 링크 : https://www.acmicpc.net/problem/8311 문제 풀이 문제를 읽으면 상태가 (1~i 까지 중에서, 부분 배열의 마지막 숫자) 와 같은 식으로 나오기 때문에 DP를 떠올리게 된다. 하지만, $A_i$ 는 단지 수 하나이기 때문에 dp[i-1] 에서 dp[i] 로 넘어갈때 dp[i][$A_i$] 만 바뀌게 되고, 따라서 2차원 DP를 할 필요 없이 그냥 부분 배열의 마지막 숫자만 들고 있으면 된다. DP[$A_i$]에 업데이트 할 값은 $ \sum_{j=1,j\neq A_i}^{N} DP[j] $ 이기 때문에 DP의 모든 칸의 합을 변수로 들고 있으면서 DP[$A_i$] 값만 빼주고 업데이트 하면 된다. 시간 복잡도는 $O(N)$ 코드 1 2 3 4 5 6 7 8 9 1..

문제 링크 : https://www.acmicpc.net/problem/12430 문제 풀이 문제를 딱 읽으면 DP향이 느껴진다. 냅색 혹은 동전으로 낼 수 있는 가격과 비슷한 느낌이지만, 정확히 허기질 때만 다른 음식을 먹을 수 있다. A[x]를 x일 동안 버틸 수 있는 지를 체크하는 것이라면 i번째 음식은 0~$P_i$ 값을 $S_i ~ P_i + S_i$에 더하는 즉, 업데이트를 하는 효과를 가지고 있다. 하지만 동전 문제와 다른 점은 한계인 $P_i$가 존재하기 때문에 업데이트하는 순서에 따라서 나오는 결과값이 달라질 것이다. 업데이트 한다는 것은 그 음식을 먹는 가능성을 주는 것이기 때문에 정답 결과가 나오는 경우 때, 음식을 먹는 순서대로 업데이트를 실시한다면 최댓값을 얻어낼 수 있다. 그렇다..

문제 링크 : https://www.acmicpc.net/problem/17670 문제 풀이 문제에 존재하는 서브태스크이자 작은 경우인 N=2 인 경우를 살펴보자. 두 명이 각각 행복도가 절반이 되는 만족할 수 있는 위치가 $x_1, x_2$ 라고 하자. 그러면 일반성을 잃지 않고, $x_1

문제 링크 : https://www.acmicpc.net/problem/5542 문제 풀이 이 문제에서 쿼리 q개를 제거해보자. 그러면 어떻게 풀 수 있을까? 이 형태의 문제를 해결하기 위해서 생각해야 하는 핵심 아이디어는 바로 결정 문제로 바꾸어서 해결하는 것이다. 목적지까지 이동하는 도중 축제랑 가장 멀리 떨어질 수 있는 거리 x 를 구하는 것은, 축제랑 거리 x이상 떨어진 노드들만 사용해서 목적지까지 이동이 가능한지를 묻는 결정 문제로 바꿔서 생각할 수 있다. 결정 문제는 어떻게 해결할까? 일단 각 노드들이 축제로부터 거리가 얼마나 떨어져 있는지를 알아야 하기 때문에 다익스트라를 먼저 실시해야 한다. 모든 축제 정점은 거리 0으로 해놓고 pq에 넣은 후에 시작하면 모든 노드에 대해서 가장 가까운 축..