PS 일지

문제https://www.acmicpc.net/problem/17471정점이 $N$개이고, 정점에 양의 정수 가중치가 있는 그래프가 주어진다. 이 그래프의 정점들을 서로 겹치지 않게 두 집합으로 분할하여 각 집합 내의 정점들끼리 연결되도록 하였을 때, 두 집합의 가중치 합 차이의 최솟값을 구해야 한다. 풀이재귀 + 비트마스킹을 이용해 가능한 두 집합을 완탐으로 구해주었다.두 집합이 정해지면, 분리 집합으로 집합 내의 연결 여부를 확인하고 답을 구해주었다. #include #include #include #include using namespace std;int r[10]{}, s[10]{}, N;int f(int x) { return x == r[x] ? x : r[x] = f(r[x]); }int an..

문제https://www.acmicpc.net/problem/12928정수 $N$과 $S$가 주어지면, 정점의 개수가 $N$개이며 길이가 $2$인 단순 경로의 수가 $S$개인 트리를 만들 수 있는지 판별하는 문제다. 두 경로가 서로 방향만 다르고 지나는 점이 동일하면 같은 경로이다. 풀이정점의 개수가 $n$개이고 길이가 $2$인 단순 경로의 수가 $s$개인 트리가 있다고 가정하자.이 트리에서 차수가 $k$인 정점에 새 정점을 이어붙이면, 단순 경로의 수는 $s+k$가 된다.구체적으로, 정점의 수가 $n$이고 길이가 $2$인 단순 경로의 수가 $s$이며, 차수가 $k$인 정점이 존재하는지 여부는 배낭으로 쉽게 알 수 있다. 위 정의대로 $d[n][k][s]$를 정의하면, $d[n][k][s] = 1$일 때..

문제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..

9/9 ~ 10/11 BOJ 4167 - Tunnelling the EarthGold 3Elapsed Time : --Rating : 1224 -> 1208 (-16) 소수점 문제인 것을 보고 도망쳤다. BOJ 10021 - Watering the FieldsGold 3Elapsed Time : 5m 36sRating : 1208 -> 1233 (+25)#mst 좌표평면에서의 기본 MST 문제이다. BOJ 7639 - Counting PixelsSilver 1Elapsed Time : 13m 16sRating : 1233 -> 1241 (+8)#math #geometry 답은 r값만으로 정해진다. 원의 방정식을 이용해서 구해주었다. BOJ 26650 - 그램팬Silver 1Elapsed Tim..

9/2 ~ 9/4골랜디도 제대로 못하는 실력임을 깨닫고 가는 날이었다. BOJ 2063 - 철사 연결Silver 1Elapsed Time : 39m 36sRating : 1244 -> 1258 (+14)#greedy #sorting 반원 모양인 건 중요하지 않고, 철사의 시작 ~ 끝의 길이가 지름임을 알면 된다.몇 개를 골랐을 때 가장 큰 것의 길이가 나머지의 합보다 작거나 같으면 YES이다.문제를 잘못 읽어서 30분동안 삽질을 했다. BOJ 4895 - Stock ChaseGold 4Elapsed Time : --Rating : 1258 -> 1216 (-42) 너무 어려웠다. pass하고 태그를 깠는데 여전히 풀 수 없었다. BOJ 23506 - CoinsGold 4Elapsed Time : ..

문제 풀이를 재미있게 해주는 랜덤 디펜스 확장 프로그램을 발견했다.매번 직접 하기 귀찮기도 해서 한 번 체험해보았다. BOJ 17827 - 달팽이 리스트Silver 2Elapsed Time : 7m 55s Rating : 1000 -> 1029 (+29)#implementation 사이클의 길이를 구해서 $K$를 적절히 $N$밑으로 내려주면 된다. BOJ 4358 - 생태학Silver 2Elapsed Time : 3m 12sRating : 1029 -> 1055 (+26)#map map으로 나온 횟수 저장 BOJ 15787 - 기차가 어둠을 헤치고 은하수를Silver 2Elapsed Time : 9m 24sRating : 1055 -> 1078 (+23)#bitmask 각각의 기차는 비트마스크를 이..

문제https://www.acmicpc.net/problem/20156 $i$번 정점의 부모가 $p_i$인 포레스트가 주어지고, 아래와 같은 쿼리가 $M$개 주어진다.$x$ : $x$와 $x$의 부모를 잇는 간선이 아직 존재한다면, 끊는다. 이 때, 아래와 같은 질의 $K$개를 처리해야 한다.$a$ $b$ $c$ : $a$번 쿼리까지 수행되었을 때, $b$와 $c$가 연결되어있는가? 풀이쿼리에 의해 끊어지는 간선들은 모두 끊어놓고 질의를 오프라인으로 처리한다.쿼리를 역순으로 수행하면 간선을 잇는 쿼리로 바뀌며, 각 질의는 분리 집합으로 해결할 수 있게 된다. #include using namespace std;using ll = long long;int root[100001]{};int find(int ..