2021.06.02 problem solving

오늘 하루만에 다이아 1, 다이아 3, 다이아 5, 플래 3을 한 문제씩 풀어서 기분이 매우 좋다.

 

BOJ 18510 : Program (solved.ac 난이도 : P3)

2번 명령이 나온 개수의 prefix sum을 저장하며 i번 명령의 마지막 위치, i번 쿼리의 dp값 세 개를 저장하면 문제를 풀 수 있다. i번째 명령이 1번이라면 p의 마지막 위치와 p의 dp값을 모두 i로 바꾼다. i번째 명령이 2번이라면 지금까지 p였을 때 없애야 할 개수와 지금까지 q였을 때 없애야 할 개수를 비교한 다음 둘 중 작은 걸 선택하면 된다. 그 후 마지막으로 dp값들과 마지막 위치와 2번 명령이 나온 개수의 prefix sum과의 관계를 잘 생각하며 식 계산을 하면 풀린다.

 

Time Complexity : O(N)

 

BOJ 17675 : 램프 (solved.ac 난이도 : D5)

예전에 풀다가 버렸던 아이디어를 다시 생각해보니 그 아이디어가 맞았었다. 좀 노가다성으로 구현했는데 간단하게 구현하는 방법이 있었다. 구현 잘하고 싶다.

두 문자열을 S, T라고 하자. 램프의 상태를 최적으로 바꾸는 방법은 다음 6가지밖에 존재하지 않는다.

1. 아무것도 바꾸지 않는 경우 ($S[i] = T[i]$일 때만 가능)

2. 동작 1을 하는 경우 ($T[i] = 0$일 때만 가능)

3. 동작 2를 하는 경우 ($T[i] = 1$일 때만 가능)

4. 동작 3을 하는 경우 ($S[i] \neq T[i]$일 때만 가능)

5. 동작 1을 한 다음 동작 3을 하는 경우 ($T[i] = 1$일 때만 가능)

6. 동작 2를 한 다음 동작 3을 하는 경우 ($T[i] = 0$일 떄만 가능)

 

나머지 경우를 생각해보자.

동작 3의 구간이 두 번 겹치는 경우는 겹치지 않게 분리된 두 번의 동작 3으로 똑같은 상태를 만들 수 있다.

동작 3을 한 다음 동작 1을 하는 경우, 동작 1이 동작 3에 포함된다면 동작 2를 한 후 동작 3을 하는 것과 같다. (동작 1과 동작 2를 바꿔도 마찬가지이다.)

동작 3을 한 다음 동작 1을 하는 경우, 동작 1이 동작 3에 포함되지 않으면 동작 1과 동작 3을 겹치지 않게 해서 똑같은 상태를 만들 수 있다. (동작 1과 동작 2를 바꿔도 마찬가지이다.)

동작 1을 한 다음 동작 2를 하는 경우, 동작 2가 동작 1에 포함되지 않으면 동작 1과 동작 2를 겹치지 않게 해서 똑같은 상태를 만들 수 있다. (동작 1과 동작 2를 바꿔도 마찬가지이다.)

동작 1을 한 다음 동작 2를 하는 경우, 동작 2가 동작 1에 포함된다면 동작 1을 한 다음 동작 3을 해서 똑같은 상태를 만들 수 있다.

 

따라서 이 6개의 상태에 대해 dp를 1부터 N까지 돌리면 최소 횟수를 찾을 수 있다.

 

Time Complexity : O(N)

 

BOJ 10008 : Polarization (solved.ac 난이도 : D3)

문제 지문을 재밌게 써놔서 가독성이 좋지 않다... 하여튼 문제 이해만 한다면 구하라는 값 자체는 간단하고, 풀이 또한 복잡하지 않다.

 

단방향 간선들이 있는 트리를 생각했을 때, 간선들을 모두 뒤집어도 이동할 수 있는 pair들 또한 모두 뒤집으면 pair의 개수는 변하지 않는다는 걸 알 수 있다. 따라서, 루트 r을 잡은 다음 각 서브트리들이 모두 조상을 향하게 하거나 모두 자손을 향하게 형태가 최적이다. 또한 이 루트 r은 트리의 센트로이드이다. 이제 각 서브트리들에 대해 트리 dp를 해주고, 들어오는 서브트리의 노드의 개수의 합이 a, 나가는 서브트리의 노드의 개수의 합이 b라고 하면 각 서브트리에서 트리 dp를 해준 값의 합에 a*b를 더하면 된다.

 

$a+b = n-1$로 일정하므로 a와 b의 차를 최소로 해야 한다. 그래서 냅색을 해야 하는데, 그냥 하면 $O(N^2)$이라서 시간초과가 난다. 냅색에서 더해주는 서로 다른 값의 종류가 최대 $O(\sqrt{N})$개이므로, BOJ 12920의 아이디어를 잘 활용하면 $O(N\sqrt{N})$ 냅색으로 해결할 수 있다.

 

대충 증명이 된 것 같긴 한데, 글로 쓰라 하면 잘 모르겠다. 문제를 푼 후 기여를 보면 증명이 잘 나와 있다.

 

Time Complexity : $O(N\sqrt{N})$

 

BOJ 10075 친구 (solved.ac 난이도 : D1)

 

이 문제는 풀이 적기가 귀찮다. 알아서 봐라. 아마 IOI 문제니까 찾으려면 쉽게 찾을 거다.