11월의 문제 풀이 - (1)
11/1 ~ 11/10에 푼 문제들입니다.
문제의 풀이가 포함되어있으니 유의하세요.
11/1
Gold 4
#knapsack
각 부분집합의 합은 $\frac{N(N+1)}{4}$가 되어야 한다. 이 값이 정수가 아니면 답은 $0$이다. 그렇지 않으면, $1, 2, \cdots, N$으로 $\frac{N(N+1)}{4}$를 만드는 경우의 수를 knapsack dp로 세어주자.
Gold 4
#bellman_ford
음수 가중치가 있는 그래프에서 최단 경로를 구해야 하므로 벨만-포드를 써주자. 벨만-포드 알고리즘의 기초 문제이다.
Gold 4
#floyd-warshall
모든 정점 사이의 최단 경로를 구하는 플로이드-워셜을 써주자. 플로이드-워셜의 기초 문제이다.
Gold 4
#floyd-warshall
플로이드-워셜을 수행할 때, 자기 자신의 비용을 $0$으로 놓지만 않으면 된다. 이렇게 해서 돌렸을 때, 최소 사이클은 $dist[i][i]$ 중 최솟값이 된다.
Gold 3
#map #set
set에 모든 접두사를 담아주고, map에 각 문자열이 몇 번 등장했는지 세주자.
Gold 2
#sorting #prefix_sum
각 구간의 시작과 끝에 +1, -1을 할당해서 정렬 후 처음 점부터 쭉 스위핑하며 prefix sum의 최댓값을 구해주자.
Gold 1
#greedy #binary_search
학생을 키가 큰 순으로 정렬하고 순차적으로 그룹에 넣는다고 해보자.
어떤 학생을 그룹에 넣은 후에는 그 학생의 등수를 더 이상 고려해줄 필요가 없다. 이후에 들어오는 모든 학생들이 키가 더 작기 때문이다.
그룹을 차례대로 $1$번 그룹, $2$번 그룹, $\cdots$라 하자.
어떤 학생 ${H, K}$를 그룹에 넣을 때, 현재 그룹 중에 구성원이 $K$명 미만인 곳에 넣어야 한다. 그런 그룹이 여러 개라면 그 중에서도 가장 그룹 구성원이 많은 곳에 넣고, 그것도 여러 개라면 번호가 가장 작은 그룹에 넣자. 만들어지는 그룹의 개수를 최소화하기 위함이다.
이렇게 하면, 각 그룹별 구성원 수는 단조감소 형태를 띄므로 이분 탐색으로 각 학생이 들어갈 자리를 찾을 수 있다.
Gold 2
#sorting #meet_in_the_middle #binary_search
$A, B$에서 나올 수 있는 모든 합을 구해 $X$에 담아주고, $C, D$에서 나올 수 있는 모든 합을 구해 $Y$에 담아주자.
$X_i + Y_j = 0$이 되는 모든 경우를 구해주자. $Y$를 정렬하면 각 $X_i$마다 가능한 $Y_j$의 개수는 upper_bound - lower_bound로 구할 수 있다.
Gold 1
#geometry
두 점을 $xy$평면에 수직으로 내려 원뿔 밑면에서의 사잇각을 구하면, $\lvert A_1 - A_2 \rvert$이다. 이 때, 최단 거리를 구해야 하므로 이 값이 $180$을 넘어간다면 반대쪽 각으로 취하자. 이 각을 $\theta$라고 하자.원뿔 전개도를 그렸을 때, 곡면의 중심각 $t$는 $2\pi : t = 2\pi \sqrt{r^2+h^2} : 2\pi r$이므로 $t = \frac{2\pi r}{\sqrt{r^2+h^2}}$이다. $p_1, p_2$가 전개도 상에서 이루는 각 $x$는 중심각의 비를 이용해 구할 수 있다. $x$와 $d_1, d_2$를 알고 있으므로 피타고라스 정리로 두 점 사이의 거리를 구할 수 있다.
11/2
BOJ 12034 - 김인천씨의 식료품가게 (Large)
Silver 5
가장 큰 금액은 반드시 할인된 금액이 아니다.
큰 금액부터 보면서 해당 금액에 매칭되는 할인된 금액을 하나씩 출력하고 배열에서 이미 사용한 금액이라는 것에 대한 처리를 해주자.
Silver 1
#dp
각 직사각형을 가로로 놓았을 때, 세로로 놓았을 때의 경우를 고려하여 dp[N][2] 테이블을 채워주자.
Gold 2
#priority_queue
우선순위 큐를 이용하면 문제의 조건에 딱 들어맞도록 간편하게 구현할 수 있다.
구조체로 우선순위 큐의 비교함수를 문제 조건에 맞게 직접 다시 정의해주면 된다.
11/3
Gold 1
#bfs #simulation
문제에서 요구하는 모든 행동을 그대로 시뮬레이션하는 코드를 작성하자. 이 과정에 클러스터 판별을 위해 bfs를 섞어줬다.
공중에 떠있는 클러스터를 몇 칸 떨궈야 하는지 세주는게 조금 복잡하다.
Gold 1
#bfs #simulation
미네랄 2 문제를 풀었더니 하나가 더 굴러들어왔다.
이 문제는 읽어보니 똑같은 문제인데, 2보다 구현히 조금 더 쉬운 케이스만 입력으로 주어진다.
Gold 1
#segtree
이게 왜 되는지 아직도 모르겠다. 몇 달 전에 이것과 똑같은 문제를 풀었었는데, 그 때는 어떻게 푼 걸까? 지금은 못 풀었다. 한 시간을 넘게 고민했는데도. 실력이 퇴화된 것 같다.
Platinum 5
#geometry #randomization
편의상, 문제에서의 $p$를 $100$으로 나눈 값을 $p$로 사용하겠다.
$np$개 이상의 점이 한 직선 위에 존재함을 보여야 한다.
설명에 앞서, 문제가 요구하는 직선이 있는 상황이라고 가정을 하겠다.
아무 점이나 두 개를 골라서 직선을 잇는 것을 한 번의 시행이라고 하자. 그 직선이 문제의 요구사항을 만족할 확률을 $x$라고 하면,
$x = \dfrac{ np( np - 1)}{n(n-1)} = p^2 + \dfrac{p(p-1)}{n-1}$이다. $p \le 1$이고, 간결하게는 $x > p^2$로 나타낼 수 있다.
한 번의 시행에서 원하는 직선을 찾지 못할 확률은 $1-p^2$보다 작다.
그렇다면, 시행을 $G$번 하면 어떻게 될까?
$G$번의 시행 중 단 한 번도 원하는 직선을 찾지 못할 확률은 $(1-p^2)^G$보다 작다. 대략 200번 시행했을 때, $1-p^2 < 0.96$이므로 찾지 못할 확률은 약 $0.96^{200} \approx 0.00028$이다.즉, 구하고자 하는 직선이 존재하지만 못 찾는 경우는 극히 희박하므로 만약 200번의 시행에서 찾지 못했다면 그 직선은 없다고 봐도 무방할 것이다.
한 번의 시행에서 그 직선 위의 점을 구하는 데 $O(N)$이고, 200번 시행을 하면 원하는 시간복잡도 내에 통과할 수 있다.
Platinum 4
#geometry #randomization
위의 문제에서 생각을 조금만 더해보자.
두 개의 직선으로 모든 점을 지날 수 있다고 가정하면, 그 중 하나의 직선은 반드시 $\frac{N}{2}$개 이상의 점을 지난다. 이 직선을 위에서 설명한 방법대로 찾고, 여기에 포함되지 않은 나머지 점들이 한 직선 위에 있는지 확인하자.
Platinum 4
#dijkstra #bitmask_dp
$X$와 $p_i$들로 다익스트라를 한 번씩 도는 것 까지는 기본적으로 생각해낼 수 있다.
이 결과들로 시작 정점을 제외하고 $p_i$와 $Y$로 구성된 정점 $P+1$개짜리 그래프를 새로 만들어줬고, 간선은 서로간의 최단 경로로 설정했다. 각 정점 $p_i$와 $Y$에 순서대로 $0, 1, 2, \cdots$의 번호를 새로 부여해줬다.
시작점 $X$를 제외한 이유는, 이 곳이 시작점이기 때문에 여길 떠나면 새로 만든 그래프 상에서 다시 돌아올 일이 없기 때문이다. (기존 그래프에서는 돌아올 수도 있지만, 이 경우는 이미 최단 경로를 구한 시점에서 포함되어있기 때문에 고려할 필요가 없다.)
문제는, 이것을 $O((P+1)!)$에 해결하기엔 시간이 모자르다는 것이다. 이걸 어떻게 풀 수 있을까만 거의 2시간 넘게 고민했다.
나의 접근 방법은 아래와 같다.
구하려는 값은 $P$보다 작은 모든 점을 방문한 뒤 $P$로 오는 최단 경로이다.
$P$값이 충분히 작기 때문에, 각 정점의 방문 여부를 $2^P$보다 작은 이진수로 고유하게 나타낼 수 있다고 생각했다.
$dist[i][k]$를 $k$ $\&$ $2^d$이 $0$이 아닌 모든 $d$($i$는 제외)를 방문하고 $i$번 정점으로 오는 최단 경로로 정의했다.
시작점 $X$를 제외했기 때문에, 각 정점의 초기 값이 되는 $dist[i][2^i]$는 $X$에서 $p_i$로 가는 최단 경로로 초기화했다.
$dist$를 위와 같이 정의했기 때문에, 아래와 같은 식을 만들 수 있었다.
$dist[i][k] = \min{(dist[d][k-2^i] + weight[i][d])}$ $((k-2^i)$ $\&$ $d > 0$인 모든 $d$에 대해)
여기서 $weight[i][d]$는 새로 만든 그래프 상에서의 $i$와 $d$를 잇는 거리이다.
이 $dist$배열에서 모든 점을 방문하고 원래의 $Y$에 해당하는 곳까지 가는 최단 경로는 $dist[P][2^{P+1}-1]$이다.
갈 수 없는 간선에 대한 처리를 overflow가 나지 않는 선에서 잘 해줘야한다.
11/4
Bronze 4
#math
$\max (0, 4N-(STR + DEX+INT+LUK))$
Silver 1
#recursion
$B$의 십의 자리가 $2, 4, 5, 6, 8$이면 답은 없다.
나머지 경우에는 재귀로 구해줬다.
11/5
Platinum 5
가능한 모든 분자, 분모 쌍을 탐색하며 기약분수를 발견하면, 해당 분모 분자의 배수 쌍에 모두 방문표시를 해 중복을 피했다.
nth_element로 값을 구해줬다.
시간을 보니.. 0.5초 제한에 496ms... 터질 코드인가..?
Gold 4
#dijkstra
$Y$와 이어진 간선들은 빼주고 $X$ 출발 다익스트라 한 번,
$Y$와 이어진 간선들을 넣고 $X, Z$ 출발 다익스트라를 돌리자.
Gold 3
#dijkstra
$X, Z$에서 다익스트라를 돌리고 모든 중간 도시 $Y$에 대해 $X -> Y$, $Z -> Y$를 봐주자.
Gold 3
#dijkstra
다익스트라를 $P+1$번 돌리자!
Bronze 3
1이 연속된 구간의 개수, 그러한 개체의 수를 이중 포문으로 구해주자.
BOJ 30455 - 이제는 더 이상 물러날 곳이 없다
Bronze 1
서로 인접하기 전까지는 이동할 수밖에 없다. 최초 거리의 parity에 따라 승자가 바뀐다.
Bronze 1
#constructive
$1\times L$은 $L$이다. $1\times 1\times \cdots \times L$도 $L$이다.
Silver 5
#sorting #greedy
바라보고 있는 방향에는 무조건 자신보다 작은 친구만 서있어야 한다.
따라서, 누군가 둘이 마주보게 되는 상황은 있을 수 없다.
여기서 가장 많이 학생을 고르려면, {왼쪽 왼쪽 왼쪽 ... 오른쪽 오른쪽} 을 보도록 학생들을 세워야 한다.
정렬해서 배정해주고, 합을 구하자.
Silver 4
각 영역에 있는 알파벳 개수들의 합이 모두 짝수이면 가능, 그렇지 않으면 불가능하다.
Gold 5
#sorting #binary_search
$O(N^2)$의 가능한 모든 현수막 밑변을 구해놓고 정렬시키자.
기둥의 길이가 주어질 때마다 밑변 배열에서 가능한 가장 큰 길이를 이분 탐색으로 뽑아오자.
Gold 3
#bfs
bfs로 컴포넌트마다 각 성별을 지정해주면서 모순이 생기는지 확인하자.
모순이 되는 경우는, 이미 성별이 지정된 녀석이 다른 성별로 지정되려할 때이다.
Gold 2
#bfs #priority_queue
bfs문제같아 보이는데, 어떻게 해야 나무와 최대한 멀리 떨어진 채로 이동할까?
우선, 각 지점에서의 나무까지의 최소 거리를 알아야 한다. $\rightarrow$ bfs 한 번으로 쉽게 구할 수 있다.
이제, bfs를 하는데 인접한 칸으로 이동할 때 나무와의 최소 거리가 최대인 점으로 먼저 이동해야 한다.
여기에 걸맞는, 우선순위 큐라는 아주 좋은 녀석이 있다. 나무와의 최소 거리를 첫 번째 원소로 갖는 최댓값 PQ를 갖고 bfs를 수행하자. 도착점을 만나면 바로 출력 후 종료하면 된다. PQ로 탐색했기 때문에, 이후에 도착점으로 오는 경로는 가장 안전한 경로가 아니다.
11/6
Gold 1
#disjoint_set #dfs
분리 집합으로 모든 간선 중 사이클을 이루는 간선 하나를 찾을 수 있다. 그 간선이 잇는 점 중 하나를 루트로 잡고 dfs로 각 점이 사이클의 일원인지 메모해주자.
사이클의 각 점을 루트로 갖고 다른 사이클 점을 포함하지 않는 서브트리를 각각 구성해주고, 쿼리로 주어지는 점이 같은 서브트리 내에 속해있는지 확인해주면 된다.서브트리 인덱싱을 잘못해줘서 계속 맞왜틀을 외쳤다. (뭐가 잘못됐는지는 아직도 모른다. 방법을 다르게 하니 맞았다.)
Gold 5
#dp
$dp[i][j]$를 $i$번 위치에서의 $j$값에 따른 최대 점수로 하자.
$j = 3$이면, $i$에서 스위치를 켰을 때,
$j = 2$이면, $i-1$에서 스위치를 켰을 때,
$j = 1$이면, $i-2$에서 스위치를 켰을 때,
$j = 0$이면, $i$가 스위치 효과를 받지 않을 때
이제, 식을 세워 풀면 된다.
Gold 2
#binary_search #prefix_sum
피자 조각이 1,000개까지만 주어짐에 주목하자.
$O(N^2)$이 가능하므로 모든 구간 합을 미리 구해놓고 시작한다.
한 쪽을 정렬시킨 후, 이분 탐색으로 $O(N\log{M})$에 답을 구해주면 된다.
구간 합을 구해서 넣어줄 때 아무것도 선택하지 않은 경우를 넣어줘야 하고, 전체의 합은 한 번만 넣어줘야 한다.
Gold 1
#dp
애매한 $N, K$ 제한 때문에 푸는데 시간이 오래 걸렸다.
우선, 경우를 아래와 같이 나눠주었다. (아래에서 $K$번이 앉는 경우는 제외한다.)
- 자유석에 아무도 앉지 않는 경우
- 자유석에 $1$번이 앉는 경우
...
- 자유석에 $N$번이 앉는 경우
자유석에 아무도 앉지 않는 경우의 수는 $K$를 기준으로 나뉘는 구역에 서 나올 수 있는 경우의 수의 곱이다.
자유석에 $i$번이 앉는 경우의 수는 $i$로 인해 나뉘는 구역들의 경우의 수의 곱과, $K$를 기준으로 $i$ 반대편 구역의 경우의 수를 곱한 값이다.
모든 경우에서 공통적으로 요구하는 값은 "자유석이나 빈 자리가 포함되지 않은 상황에서의 자리 배치 경우의 수"이고, 이 값은 오직 해당 구간의 길이에만 영향을 받는다. 따라서, 길이를 $g$라고 할 때 이 값을 $F(g)$라고 하겠다.
길이 $g$인 구간에서의 경우의 수를 구해보자. 인접한 두 쌍을 swap하는 연산을 서로 인덱스가 겹치지 않게 하는 경우의 수이다.
길이가 $g$이면, swap 횟수의 최댓값은 $\lfloor \frac{g}{2} \rfloor$이다.
조금 더 쪼개어 생각해보자.
길이가 $g$이고, swap 횟수를 $k$번 부여할 때, 가능한 경우의 수를 $H(g, k)$라고 하자.
그러면, $F(g) = 1 + H(g, 1) + H(g, 2) + \cdots + H(g, \lfloor \frac{g}{2} \rfloor )$이다.
$H(g, k)$는 어떻게 구할까?
우선, $k = 1$인 경우를 보면 $H(g, 1) = g-1$임은 쉽게 알 수 있다.
길이 $g$에서 swap을 $k$번 하는 경우의 수는 길이가 $g-2$인 곳에서 swap을 $k-1$번, 길이가 $g-3$인 곳에서 swap을 $k-1$번, ... 길이가 $2k-2$인 곳에서 swap을 $k-1$번 하는 경우의 수의 합과 같다.
따라서, $H(g, k) = H(g-2, k-1) + H(g-3, k-1) + \cdots + H(2, k-1)$로 재귀적으로 구성이 가능하다.
이 $F, H$를 이용해서 전체 경우의 수를 적절히 구해주자.
Gold 3
#dijkstra
$X$에서 $Y$로 가는 모든 경로 중, 경로 상에 존재하는 가중치의 최솟값이 최대가 되는 경우를 구해야 한다.
다익스트라를 약간 변형하여, 최대 힙에서 현재 정점의 max값을 갱신해주는 방식으로 구현하면 된다.
Gold 2
#greedy #constructive
큰 수가 최대한 일찍 나오도록 배치해야 한다.
첫 번째로 나오는 사과가 가장 커지려면, 반드시 $2N-3$이어야 한다. 이 때, 양 끝의 네 곳에는 $2N-3, 2N-2, 2N-1, 2N$이 있어야 한다.
나머지 사과들은 어떻게 배치해야 최적일까?
$2N-3$이 처음에 뽑히면, 다음은 반드시 $2N-4$가 뽑히도록 하자. $2N-4$부터 1씩 줄이면서 $N-2$개의 사과를 1번 튜브에 넣고, 마지막에 $2N-2$를 넣자.
그러면, 사과를 빼는 작업은 항상 1번 튜브에서만 이루어지며, 최종적으로 1번 튜브가 비어버리고 2번 튜브엔 $N$개의 사과가 남는다.
똑같이, $2N-1, 2N$을 양 끝에 두고 아직 넣지 않은 사과 중 크기가 큰 순서대로 $2N-1$뒤로 이어붙이면 된다.
Gold 1
#meet_in_the_middle
$n \le 40$이다. 문제에서 대놓고 meet in the middle을 써달라고 하고 있다.
사이즈를 반으로 나눠 각각의 구간에서 나올 수 있는 모든 경우 $2^{n/2}$가지를 구해서 저장해놓고, 이분 탐색으로 찾으면서 합이 $K$인 걸 찾으면 추적해주자.
Platinum 5
#two_pointers
가장 위에 있는 행에서 갈 수 있는 칸들을 모두 찾아주자. 이 칸들은 모두 반드시 하나의 구간 $[s, e]$에 속한다.
행을 내려가면서, $[s, e]$를 조절해주자.
$[s, e]$ 구간에 대해,
- 가장 오른쪽에 있는 'U'가 새로운 $e$가 된다.
- 가장 왼쪽에 있는 'U'에서부터 구간 밖의 그 다음 'U'의 한 칸 오른쪽이 새로운 $s$가 된다.
만약, 해당하는 곳을 못 찾을 시에는 바로 탐색을 종료한다.
이걸 직접 한 칸씩 이동시키기엔 행의 개수가 너무 많다.
미리 인덱스를 $O(MK)$에 구해놓고 시작하자.
Gold 2
#sorting #prefix_sum
크기가 작은 순서대로 하나씩 봐주면 된다. 각 색깔 별로 현재까지 나온 크기의 합을 따로 관리해주자.
같은 크기의 공에 대해서는 계산하면 안 되므로 적절히 빼놨다가 다시 넣어주자.
BOJ 12011 - Splitting the Field
Gold 1
#geometry #sorting
울타리에 의해 나눠지는 점을 $x$축 정렬, $y$축 정렬 각각에 대해 따로 구해주자. 각 구간의 최대, 최소 좌표를 가지고 반복문 한 번으로 두 울타리의 넓이를 구할 수 있다.
Platinum 5
#segtree #sorting #binary_search
소의 위치를 기준으로 정렬한 후, 높이의 최댓값을 구성하는 세그먼트 트리를 만들자.
각 소마다, 위치의 차이가 $D$ 이내인 소 중에 좌, 우 각각 $2h_i$ 이상인 소가 있는지 봐주면 된다.
11/7
Gold 2
#dfs #tree
트리의 지름 / 2이다.
Gold 1
#tree #graph_traversal #set
주어지는 각 줄마다, 트리를 직접 만들고 preorder의 경로를 구해 set에 담아주면 개수가 저절로 세어진다.
11/8
Platinum 3
#meet_in_the_middle #bitmask
팀 1에 모든 선수를 배정하고, 팀 2에서 $\frac{N}{2}$명을 골라서 빼주는 방식으로 구현하면 된다. 배열을 반으로 갈라서 각 구간에서 선수를 고르는 모든 경우를 저장하고, 합쳐서 $\frac{N}{2}$명이 되는 경우를 이분 탐색으로 봐주면 된다.
방문 여부는 시간초과가 날까봐 bitmask로 저장했다.
사전 순으로 출력하라는 조건 때문에 많이 헤맸다.
Platinum 1
#hld #segtree #offline_query
필요로 하는 우유 종류를 기준으로 쿼리를 정렬해주고, 해당 종류의 번호까지만 정점 값을 세그에 update 해준다.
max segtree로 구성하면 해당 경로에 값이 존재하는지 알아낼 수 있다.
트리에서의 경로를 구해야 하므로 hld를 사용하면 된다.
Diamond 4
#mst #hld #lazyprop
한 달 전에 보고 못 풀겠어서 버려놨던 문제를 다시 풀어봤다.
최초에 MST를 구성하고, 이를 $G$라고 하자.
$G$에 속하지 않은 모든 간선 $E(u, v)$는 $G$ 상에서 $u$와 $v$를 잇는 경로에 존재하는 간선이 하나 사라졌을 때 그것의 대체 간선이 될 수 있다.
min segtree에서 그 경로에 해당하는 구간에 $E$의 가중치를 뿌려주자.
답을 구할 때는 segtree에서 값을 가져오고, 이 값이 초기값이면 대체 간선이 없다는 것이므로 -1이다.
11/9
Silver 5
#calculus
부피는 $V = b(a-2b)^2$이다. 이 때, $V$가 최대가 되는 $b$를 찾아야 한다.$V' = (a-2b)^2 - 4b(a-2b)$이고, 이 값이 $0$이 되는 $b$의 값은 각각 $\dfrac{a}{6}, \dfrac{a}{2}$이다.
$b = \dfrac{a}{2}$이면 밑변 $a-2b = 0$이 되므로 가능할 수 없다. 또, 그 b는 부피의 극솟값을 가리키므로 될 수 없다.
따라서, $b = \dfrac{a}{6}$이다.
11/10
Gold 3
#set #bruteforcing
한 열쇠는 x, y축 반전을 통해 총 4개의 동형을 가진다.
각 열쇠마다 동형을 모두 구해, 그 열쇠가 지금까지 나온 적이 있는지 판별하자.
Gold 4
바로 전 단계의 대소 관계를 기억하고 있으면, 현재 원소를 추가했을 때도 부분배열이 되는지의 여부를 알 수 있다.
부분배열에 여전히 속한다면, 그 길이만큼 정답에 더해준다.
Gold 3
#birthday_problem
$500\,000$개의 수 중, 중복되는 수가 하나라도 있으면 답은 그 두 개의 수로 정해진다. 그럴 확률을 구해보자.
$1 - ($모두 다른 수일 확률 $ = P)$ 이고, $P$를 구해보자.
각 수가 나올 확률은 $\dfrac{1}{2\,000\,000\,000}$으로 동일하니까, $P = \dfrac{_{2\,000\,000\,000}C_{500\,000}}{_{2\,000\,000\,000}H_{500\,000}}$이다. 이 값은 매우 작은 수이다.
다시 말해, $1 - P$는 거의 $1$에 가깝다. 즉, 주어지는 경우에서 중복되는 수는 항상 있다고 봐도 무방하다.
Platinum 1
#meet_in_the_middle #binary_search
naive하게 계산하면 경우의 수가 $\dfrac{38!}{19!19!} = $ 거의 300억에 가까워서 시간 초과를 받는다.
$1 \le k \le n$인 $k$에 대해 시작점에서 $(k,n-k+1)$로 가는 길과, 도착점에서 $(k,n-k+1)$로 가는 길을 각각 따로 저장해두면 각 경우의 수는 $\sum \limits_{k=0}^{n-1} {\dfrac{(n-1)!}{k!(n-1-k)!}} = 524\,288$이다.
경우를 합쳐줄 때, 두 구간의 max sum이 $K$보다 작은 경우를 골라내고, 두 구간을 합쳤을 때의 최대 부분합이 $K$보다 작은 경우는 이분 탐색으로 구해주자.