alogrithm

백준 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..