백준
BOJ-10803 정사각형 만들기(증명)
https://www.acmicpc.net/problem/10803 10803번: 정사각형 만들기 두 변의 길이가 모두 양의 정수인 직사각형 모양의 종이가 주어져 있다. 이 종이를 칼로 여러 번 잘라서 모든 조각이 한 변의 길이가 양의 정수인 정사각형이 되도록 하고자 한다. 칼로 종이를 www.acmicpc.net dp로 모든 n, m에 대하여 구하면 TLE를 받기에 뭔가의 조건으로 시간복잡도를 줄여야한다. 대부분의 풀이는 $WLOG \ n \leq m$ 에 대해 $ 3n \leq m$의 조건에 대하여 $dp[n][m] = dp[n][m-n] + 1$을 해주고 있다. 이렇게 타이트한 조건에 대해선 증명하지 못하였고 정당성에 대해서도 잘 모르겠다. 찾은 조건은 $m >= \frac{n^2}{3}$ 에 대하..
백준 1199번 - 오일러 회로
https://www.acmicpc.net/problem/1199 1199번: 오일러 회로 첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러 www.acmicpc.net # Approach) 오일러 회로를 구성하는 알고리즘, Hierholzer's Algorithm에 대해 배우는 문제이다. # Logic) Hierholzer's Algorithm을 그대로 적용하자. TLE를 피하기 위하여 본 포스트에서는 인접행렬대신 인접리스트를 이용하여 구현할것이다. 1. 간선의 정보를 저장해준다. 각각의 간선의 정보를 간선의 리스트 edges에 넣어준후, 각 정..
백준 7579번 - 앱
https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net # Approach) 제한 된 두가지의 자원(메모리, 비용)중 하나를 최소화하며 다른 하나를 최대화 해야한다. 고로 Knapsack 알고리즘을 떠올리자. dp배열을 어떻게 잡을지가 이 문제의 포인트이다. $dp[N][M]$ 으로 메모리를 채워가는경우 $O(n) = N \times M = 10^2 \times 10^7 = 10^9$으로 터질 가능성이 있다. 따라서 $ dp[N][sum(c)]$, $sum(..
백준 19565번 - 수열 만들기
https://www.acmicpc.net/problem/19565 19565번: 수열 만들기 문제 지문에 쓰여 있는 조건을 만족하는 가장 긴 수열을 $A$라 하자. 첫째 줄에는 $A$의 길이를 출력한다. 둘째 줄에는 $A$의 원소들을 출력한다. 이러한 수열이 여러 개일 경우 아무거나 출력한다. www.acmicpc.net # Approach) $For$ $1 \leq i < j \leq |A| $, $A_{i} \neq A_{j}$ $\lor A_{i+1} \neq A_{j+1}$ $\iff$ $ \lnot \left(A_{i} = A_{j} \land A_{i+1} = A_{j+1}\right)$ $\iff$ $\lnot \left(\left\{ A_{i}, A_{i+1} \right\} = \lef..
백준 1006번 - 습격자 초라기
https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net # Approach) 타일링문제와 상당히 흡사하다. 고로 DP를 떠올려보자. First Try(Failed) # Definition) $dp[i][j] :$ $min \ value \ when$ $inner \ circle \ is$ $filled \ to \ index \ i$, $and \ outer \ j$ $in[i] :$ $cost \ of \..