2022.02.01 설날맞이 PS 일지

작성일 | In

서론

2022년 설날을 기념해 BOJ에서 민속놀이 관련 문제들을 풀어보았습니다.

문제 목록

BOJ 문제집

  • 줄다리기
    • BOJ 2488 줄다리기
  • 윷놀이
    • BOJ 2490 윷놀이
    • BOJ 17825 주사위 윷놀이
    • BOJ 12425 윷놀이 (Small)
    • BOJ 12426 윷놀이 (Large)
    • BOJ 15778 Yut Nori
  • 장기
    • BOJ 16509 장군
    • BOJ 1846 장기
    • BOJ 23041 뛰는 기물
  • 스타크래프트
    • BOJ 1002 터렛
    • BOJ 12869 뮤탈리스크
    • BOJ 12870 뮤탈리스크 2
    • BOJ 1031 스타 대결
    • BOJ 1608 스타 대회
  • BOJ 18890 Seollal

2488 줄다리기

배열의 앞과 뒤에서 각각 조건을 만족하는 구간을 찾은 다음, 가운데 구간이 조건을 만족하는지 확인하면 될 것 같다는 생각을 할 수 있습니다. 조건을 만족하는 Prefix를 찾는 방법을 알아봅시다.

편의상 $X_i = \sum_{k=1}^{i} A_k,\ Y_i = \sum_{k=1}^{i} B_k$라고 정의합시다. 각 $i$마다 $\vert X_i - Y_j \vert \leq 50$을 만족하는 $j$를 찾을 것입니다. 즉, $X_i-50 \leq Y_j \leq X_i+50$을 만족하는 $j$를 찾아야 합니다.
이때 $X_i - 50 \leq Y_j$를 만족하는 $j$는 $i$가 증가함에 따라 단조증가하고, $\vert X_i-Y_j\vert \leq 50$을 만족하는 $j$는 구간을 이룹니다. 그러므로 투포인터를 이용해 구간의 시작점을 구한 뒤, 조건을 만족하는 구간의 끝점까지 모두 훑어주면 됩니다. 배열의 원소는 20 이상이므로 $i$마다 조건을 만족하는 $j$는 최대 6개 존재하고, 모든 Prefix를 $O(N+M)$ 시간에 구할 수 있습니다. Suffix는 인덱스를 반대로 보면 되고, 마찬가지로 $O(N+M)$에 구할 수 있습니다.

$-50\leq k \leq 50$인 $K$에 대해 $X_i - Y_j = k$을 만족하는 가장 앞에 있는 Prefix의 마지막 인덱스를 각각 $Pi_k, Pj_k$, 가장 뒤에 있는 Suffix의 첫 인덱스를 각각 $Si_k, Sj_k$라고 합시다. 모든 $-50 \leq u,v \leq 50$를 보면서, 중간 구간인 $A[Pi_u+1\cdots Si_v-1]$과 $B[Pj_u+1\cdots Sj_v-1]$이 조건을 만족하는지 확인하면 문제를 해결할 수 있습니다.

시간 복잡도는 Prefix와 Suffix를 구하는데 $O(N+M)$, 중간 구간을 확인하는데 $O(100^2)$이 걸리므로 $O(N+M)$입니다.

2490 윷놀이

단순 구현 (코드)

17825 주사위 윷놀이

완전 탐색 (코드)

12425/12426 윷놀이

$D(i, player, a_1, a_2, b_1, b_2) := $ $i$번째 윷을 $player$가 던진 직후에 첫 번째 플레이어의 말이 $a_1, a_2$, 두 번째 플레이어의 말이 $b_1, b_2$에 있을 수 있으면 1, 없으면 0으로 DP 돌리면 될텐데 짜기 싫어서 안 짰습니다.

15778 Yut Nori

구현 노가다 (코드)

16509 장군

BFS 연습 문제 (코드)

1846 장기

$i < N$일 때 $(i,i+1)$, 마지막 행에는 $(N,1)$에 차를 배치한 다음, 대각선 위에 있는 것들만 적절히 옮기는 방식으로 문제를 해결할 수 있습니다.

(Method 1) $(N, 1)$은 대각선에 포함되므로 $N-2$번째 행과 교환합시다.
현재 상황은 $i \leq N-3$일 때 $(i, i+1)$, 그리고 $(N-2,1)$, $(N-1,N)$, $(N,N-1)$에 차가 배치되어 있습니다. $N=5$ 상황을 손으로 그려보면 올바른 배치임을 확인할 수 있습니다.

$(i, j)$가 대각선 위에 있는 것은 $i = j \lor i+j=N+1$과 동치입니다. Method 1에서 $i=j$가 성립하는 경우는 $N = 3$일 때의 $(N-2, 1)$ 밖에 없습니다. $N=3$일 때는 정답이 존재하지 않으므로 예외 처리를 합시다.
Method 1에서 $i+j=N+1$이 성립하는 경우는 $i=N/2$일 때 $(i, i+1)$ 밖에 없습니다. 이건 어떻게 처리해야 할까요?

(Method 2) $N$이 짝수일 때 $(N/2, N/2+1)$은 대각선에 포함되므로 $1$번째 행과 교환합시다.
현재 상황은 $2\leq i \leq N-3, i\neq N/2$일 때 $(i, i+1)$, 그리고 $(1, N/2+1)$, $(N/2, 2)$, $(N-2, 1)$, $(N-1, N)$, $(N, N-1)$에 차가 배치되어 있습니다.

Method 2는 $4$를 제외한 모든 짝수 $N$에서 올바른 답을 출력합니다. $N = 4$일 때만 손으로 직접 만들면 문제를 해결할 수 있습니다.

23041 뛰는 기물

정수론 냄새가 납니다.
격자를 $\gcd(N,M)$칸씩 분할하면, 기물은 같은 영역 안에 있는 다른 칸에 도달하지 못합니다. 그러므로 $N/\gcd(N,M),\ M/\gcd(N,M)$인 문제를 풀고 $gcd(N,M)^2$을 정답에 곱하면 됩니다.

이제 $N, M$이 서로소인 문제를 풀어봅시다. 일반성을 잃지 않고, $N \leq M$이라고 합시다.
만약 $N = M = 1$이면 체스의 비숍처럼 이동하기 때문에 $N+M$의 기우성이 항상 유지되어서 정답은 2입니다. $N = 0$이면 $M = 1$이고, 정답은 1입니다. 이제 $1 \leq N < M$이라고 가정해도 됩니다.

여기에서 바로 규칙을 찾는 것은 어려워 보입니다. 유클리드 호제법처럼 문제를 더 작은 수로 “축소”할 수 있는지 생각해봅시다.

$1 \leq N < M$은 $2N < M$, $2N = M$, $M < 2N$ 총 3가지 경우로 나눌 수 있습니다.
$1 \leq N < 2N < M$이면 $(0, 0) \rightarrow (N,M) \rightarrow (N+M, M-N) \rightarrow (N, M-2N)$으로 최댓값을 감소시킬 수 있습니다.
$1 \leq N < M < 2N$이면 $(0,0) \rightarrow (M,N) \rightarrow (N+M, N-M) \rightarrow (N, 2N-M)$으로 최댓값을 감소시킬 수 있습니다.

$(N,M)$을 $(N,M-2N)$ 또는 $(N,2N-M)$으로 바꾸는 연산을 해도 최대 공약수는 바뀌지 않습니다. 그러므로 $1 \leq N,\ N \neq M,\ M \neq 2N$이면 항상 위 두 연산을 적용해 최댓값을 줄여나갈 수 있습니다.
만약 $N = 0$이 되어서 끝난다면 $N = 0,\ M = 1$이므로 정답은 1입니다.
$N=M$이 되어서 끝난다면 $N=M=1$이므로 정답은 2입니다.
$M=2N$이 되어서 끝난다면 $N=1, M=2$, 즉 馬가 되므로 정답은 1입니다.

한 가지 더 관찰해야 하는 사실은, $(N,M)$을 $(N,M-2N)$ 또는 $(N,2N-M)$으로 바꾸는 연산을 해도 두 수의 합의 기우성이 유지된다는 점입니다.
$N=0,\ M=2N$으로 끝나는 경우에는 $N+M$이 홀수이고, 정답은 1입니다.
$N=M$으로 끝나는 경우에는 $N+M$이 짝수이고, 정답은 2입니다.

1002 터렛

원의 방정식 (코드)

12869/12870 뮤탈리스크

12869는 SCV가 최대 3개 있으므로 “$D[h_1][h_2][h_3] := i$번째 SCV의 남은 체력이 $h_i$일 때 필요한 공격 횟수의 최솟값”으로 DP를 하면 $O(60^N)$에 문제를 해결할 수 있습니다. 상태가 $O(60^N)$가지 존재하고, 각 상태마다 $3!$가지의 상태 전이를 계산해야 하기 때문입니다.

12870은 SCV가 최대 20개 있으므로 더 효율적으로 해결해야 합니다. 답을 $L$이라고 고정해서 파라메트릭 서치를 해봅시다. $i$번째 SCV의 체력을 $H_i$, 대미지가 9, 3, 1인 공격 횟수를 각각 $A_i, B_i, C_i$라고 하면, 우리는 아래 조건을 만족하는 가장 작은 $L$을 찾아야 합니다.

  • $9A_i + 3B_i + C_i \geq H_i$
  • $\sum A_i \leq L,\ \sum B_i \leq L,\ \sum C_i \leq L$
  • $\forall i,\ A_i+B_i+C_i \leq L$

그러므로 $D(i,j,k)$를 “대미지가 9인 공격과 3인 공격을 각각 $j, k$번 했을 때, $1\cdots i$번째 SCV를 모두 죽이기 위해 필요한 대미지 1짜리 공격 횟수의 최솟값”으로 정의해서 DP를 할 수 있습니다. $L$은 항상 $7N$ 미만이므로 상태는 최대 $O(N^3)$개 존재합니다.

상태 전이는 $D(i,j,k) \leftarrow \min\lbrace D(i,j,k),\ D(i-1,j-a,k-b)+c\rbrace$ 와 같이 할 수 있습니다. 조건을 만족하는 $0 \leq a \leq j \leq L, 0 \leq b \leq k \leq L$에 대해 모두 계산해야 하므로, 각 상태마다 $O(L^2) = O(N^2)$가지 상태 전이를 계산해야 합니다.

전체 시간 복잡도는 상수가 큰 $O(N^5)$이고, 반복문 범위를 적당히 잘라주면 문제를 해결할 수 있습니다.

1031 스타 대결

가능한 대진표를 아무거나 출력하는 것은 간단한 최대 유량 문제입니다. 하지만 사전순 최소 조건이 있기 때문에 간단하지 않은 문제가 되었습니다.
$O(N^6)$ 풀이와 $O(N^4)$풀이가 있고, 두 풀이 모두 통과됩니다. 차례대로 소개합니다.

$O(N^6)$ 풀이는 사전순 최소를 구할 때 자주 사용하는 테크닉입니다. 앞에서부터 차례대로 보면서, 0으로 만들 수 있으면 0을 출력하고, 0으로 만들 수 없으면 1을 출력하는 방식으로 진행합니다. $(i, j)$의 결과를 결정할 때, $(i, j)$보다 사전순으로 큰 간선들만 사용해서 최대 유량을 동일하게 만들 수 있다면 0을 출력하고, 만들 수 없다면 1을 출력하면 됩니다.
Dinic’s Algorithm을 사용한다고 가정하면, 최대 유량을 $O(N^2)$번 구해야 하므로 $O(N^6)$입니다. 제 코드는 368ms로 넉넉하게 통과되던데, 난이도 의견을 보면 시간 초과를 받으신 분들도 계신 것 같습니다. 최적화를 신경써서 코딩을 해야 합니다.

$O(N^4)$ 풀이는 네트워크 플로우 문제에서 흔히 보이는 테크닉을 사용합니다. 일단 가능한 대진표를 아무거나 만듭니다. 그 다음에 만약 $(i, j)$가 1이라면, $S\rightarrow i \rightarrow j \rightarrow T$ 경로에 흘린 유량을 취소시킨 뒤, $(i, j)$보다 사전순으로 큰 간선을 이용하는 증가 경로가 있는지 탐색합니다. 만약 그러한 증가 경로가 있다면 그 경로로 유량을 흘려야 사전순으로 더 작은 결과물을 얻을 수 있습니다.
증가 경로를 찾는 것은 BFS를 이용해 $O(N^2)$에 할 수 있고, 최대 $O(N^2)$번 하므로 전체 시간 복잡도는 $O(N^4)$입니다.

1608 스타 대회

만약 $a$에서 $b$까지 가는 경로가 존재한다면 $a$는 경로 위에 있는 다른 모든 정점을 이길 수 있습니다. 그러므로 같은 SCC에 속한 정점들을 동등하게 생각할 수 있습니다. 이제 DAG에서 문제를 해결해봅시다.

만약 $a$에서 $b$로 가는 경로가 존재하면서 $b$가 우승할 수 있다면 $a$도 우승할 수 있습니다. 그러므로 in-degree가 0인 정점은 항상 우승할 수 있습니다.
만약 $a$에서 $b$로 가는 간선이 존재하지 않으면서 $a$가 우승할 수 있다면 $b$도 우승할 수 있습니다. 그러므로 어떤 정점 $v$보다 위상 정렬 상으로 앞선 정점들 중, $v$로 가는 간선이 존재하지 않는 정점이 우승할 수 있다면 $v$도 우승할 수 있습니다.

이 성질을 이용해 정점을 위상 정렬 순서대로 보면서, 현재 단계 이전까지 우승할 수 있는 정점의 개수를 관리해주면 문제를 해결할 수 있습니다.
만약 간선의 방향을 무시했을 때 컴포넌트가 여러 개 존재한다면 모든 정점이 우승할 수 있습니다.

18890 Seollal

문제를 간단하게 요약하면, O 또는 X가 적혀 있는 격자 그래프에서 간선을 적당히 연결해 O으로만 구성된 트리를 만들어야 합니다. 이때 0-based 기준 $i+j$가 홀수인 정점만 리프 정점이 될 수 있습니다. 또한, $(0,0)$이 루트 정점이며, 루트 정점은 차수가 1이더라도 리프 정점으로 취급하지 않습니다.

루트가 아니면서 리프가 될 수 없는 정점의 차수는 항상 2 이상입니다. 그러므로 $i+j$가 짝수인 정점의 차수가 2인 포레스트를 구한 뒤, 트리가 될 때까지 다른 간선을 추가하면 문제를 해결할 수 있습니다. 만약 $i+j$가 짝수인 정점의 차수가 2인 포레스트를 구할 수 없다면 NO를 출력하면 됩니다.

특정 정점의 차수가 2인 포레스트를 구하는 것은 Graphic Matroid와 Partition Matroid의 교집합을 구하는 것과 동일합니다. 그러므로 “$i+j$가 짝수의 정점 개수의 2배”와 “두 매트로이드의 교집합의 크기”가 동일하지 않다면 NO를 출력하고, 동일하면 트리가 될 때까지 다른 간선을 추가하면 됩니다.