PS 일지

문제https://www.acmicpc.net/problem/23594정점이 $N$개인 그래프를 구성하려 한다.그래프 상에서 서로 이동 가능해서는 안되는 정점 쌍이 $K$개 주어지고, 그래프에 사용할 후보 간선이 $M$개 주어진다.후보 간선들을 주어진 순서대로 하나씩 보면서, 그래프 상에 존재해도 되는 간선이면 사용하고 그렇지 않다면 그냥 넘어간다.이 때, 사용되는 간선들을 모두 구해야 한다.풀이각 정점별로, 해당 정점에서 갈 수 있는 정점들의 목록 $V$와, 해당 정점으로부터 도달해서는 안되는 정점의 목록 $S$를 정의하고 관리해보자. 후보 간선들 중, 현재 보고있는 간선을 $(a,b)$라고 하자.정점 $a$와 $b$가 그래프 상에서 이미 서로에게 도달 가능한 상태이면, 해당 간선은 당연히 사용 가능하..

문제https://www.acmicpc.net/problem/13215길이가 $N$인 수열 $A$와 정수 $K$가 주어지면, $1 \le l \le r \le N$이면서 $\sum \limits_{i=l}^{r} {A[i]} \ge K$인 $(l,r)$ 쌍의 수를 구하는 문제이다. 풀이$l = 1$인 쌍의 수를 어떻게 구할 지부터 생각해보자.$S[i] = S[i-1] + A[i]$ $(i > 1)$ 라고 정의하면, $S[i] >= K$인 $i$의 개수가 된다. 그럼, $l = 2$인 쌍의 수는 어떻게 구할까?기존의 배열 $S$에서 $S[1]$을 삭제하고, 모든 원소에 $A[1]$씩 뺀 후 $K$ 이상인지 검사하면 된다.거꾸로 생각하면, 기존의 배열 $S$에서 $S[1]$을 삭제하고, $K + A[1..

문제https://www.acmicpc.net/problem/20127 길이가 $N$인 수열 $A$가 주어지면,앞의 $K$개 원소를 맨 뒤로 옮겨서 단조수열을 만들 수 있는지 판단하고 가능하다면 $K$의 최솟값을 찾아야 한다.풀이증가하는 횟수를 누적한 배열 $P$와, 감소하는 횟수를 누적한 배열 $Q$를 생각해보자. $P[i] = P[i-1] + \begin{cases} 1 & A[i] - A[i-1] \geq 0 \\ 0 & \text{otherwise} \end{cases}$ $Q[i] = Q[i-1] + \begin{cases} 1 & A[i] - A[i-1] \leq 0 \\ 0 & \text{otherwise} \end{cases}$ 우선, $P[N]$ 혹은 $Q[N]$이 $N$과 같다면 답은 ..

문제https://www.acmicpc.net/problem/13244 그래프가 주어지면, 트리인지 아닌지 판별하는 문제다.multiedge가 주어질 수 있다는 점에 유의해야 한다.풀이트리인지 판별하는 가장 간단하고 쉬운 방법은 분리 집합을 이용하는 것이라 생각한다.union 연산이 정확히 N-1번 발생함과 동시에 간선의 개수가 N-1개라면, 주어진 그래프는 트리이다. #include #include #include using namespace std;int main() { cin.tie(0)->sync_with_stdio(0); int T, N, M, a, b, r[1001]{}; function f = [&](int x) -> int { return x == r[x] ? x : r[x..