2026 카카오그룹 신입크루 공채 코딩 테스트 2차 풀이

1. 힌트권

문제 요약

$1, 2, \cdots, n(n \le 16)$개의 문제를 순서대로 풀어야 한다. $k(k \le 16)$개의 힌트 번들이 주어지는데, 각 번들은 최대 한 번 구매할 수 있으며 $(a_i, p_i, b_{i1}, b_{i2}, \cdots, b_{iM})$으로 구성되어 있다. $a_i$번 문제를 풀고 난 후에 $p_i$의 비용으로 구매할 수 있으며, 총 $m$개의 힌트권이 들어있음을 의미한다. 힌트권은 어떤 문제에 대한 힌트권인지를 의미하는 정수 $b_j$로 이루어져 있다.

한 문제당 최대 $n - 1$번 힌트권을 사용할 수 있고, $i$번 문제에 대해 $j$번 힌트권을 사용했을 때 소모되는 비용은 $c_{ij}$이다. 모든 문제를 해결하는데 필요한 최소 비용을 구해보자.

풀이

각 번들은 최대 한 번 구매할 수 있으므로 $2^k$ 경우의 수에 대해서 문제를 해결합니다. 힌트권은 사용가능한 문제가 정해져 있으므로 현재 가지고 있는 힌트권이 있다면 모두 사용하는 것이 최적해입니다.

아직 힌트권을 얻지 못한 상태인데 사용하지 않도록 유의하고, 최대 $n - 1$번 사용 가능한것에 유의합니다.

2. 채굴

문제 요약

인터랙티브 문제. $a_1, a_2, \cdots, a_N(N \le 200, a_i \le 100\, 000)$이 주어질 때, $1, 2, \cdots, N$중 하나의 인덱스에 보물이 위치함. $\text{excavate}(i)$ 를 호출하면 $i$번이 보물인 경우 0, $i$번보다 왼편에 보물이 있다면 -1, 오른편에 있다면 1을 반환함. 비용은 $a_i$. 총 비용이 $k (k \le 20\, 000)$이 되도록 보물을 찾아보자. 호출 횟수나 비용을 최소화할 필요는 없다.

채점기는 적응적이며, $k$이하의 비용으로 운에 의존하지 않고 100% 확률로 찾을 수 있는 경우만 주어짐.

풀이

프로그래머스 플랫폼이 많이 바뀐 것 같습니다. 인터랙티브 유형은 고사하고 스페셜 저지도 지원하지 않았었는데 이런 문제가 출제될거라고는 생각도 못했습니다.

3. 선인장

문제 요약

$n \times m (1 \le n, m \le 500\, 000; n \times m \le 500\, 000)$ 크기의 격자 위에 $k (k \le n \times m)$개의 빗방울에 대한 일정이 주어진다. $(x_1, y_1), (x_2, y_2), \cdots, (x_k, y_k)$는 각각 $i$ 시각에 $(x_i, y_i)$ 칸에 빗방울이 떨어짐을 의미한다. $(x_i, y_i)$는 서로 다르다.

$h \times w$ 크기의 부분 격자에 대해서, 격자 내에 가장 최초로 빗방울이 떨어지는 시점을 구할 수 있다. 가능한 부분 격자 중에서 이 값이 최대가 되는 부분 격자를 구해보자.

풀이

$a_{ij}$를 $(i, j)$에 빗방울이 떨어지는 시각으로 정의합니다. 빗방울이 떨어지지 않는다면 $10^9$.

$h = 1$인 경우만 가정하면 길이가 $w$인 부분 수열의 최솟값에 대해서 가장 큰 값을 구하는 문제로 변합니다. 구간 최솟값은 여러 방법으로 $\mathcal{O}(k)$시간보다 빠르게 구할 수 있습니다.

$d_{ij}$를 $a_{ij}, a_{ij + 1}, \cdots, a_{ij + w - 1}$의 최솟값으로 정의한다. 이제 $d_{ij}$를 column-wise하게 순회하면서 똑같이 구간 최솟값 구해서 업데이트 합니다. 이제 $d_{ij}$는 $(i, j)$를 왼쪽 위로 하는 $h \times w$ 크기의 부분 격자의 최솟값이 됩니다.

4. 반복 수열

문제 요약

$a_1, a_2, \cdots, a_N (N \le 100\, 000;1 \le a_i \le 100\ 000)$이 주어질 때, 이를 이용해서 반복 수열 $b$를 만들 수 있다. 반복 수열은 $a_i$를 순서대로 $a_i$번씩 반복해 나열한 수열이다.

예를 들어 $a = 2, 1, 5, 3$ 이라면 $b = 2, 2, 1, 5, 5, 5, 5, 5, 3, 3, 3$이다. 단, 반복 수열의 원소 총합은 $10^{15}$이하이다.

정수 $l, r(l, r \le 10^{15})$가 주어질 때, $b_l +b_{l + 1} + \cdots + b_r$ 를 구하고 이를 $k$라고 하자. 이제 $b$의 부분 배열의 합이 $k$인 경우의 수도 구해보자.

풀이

$a^2_1, a^2_2, \cdots, a^2_N$을 이용하면 $l, r$이 주어질 때 $b_l, b_r$이 무슨 값인지 알아낼 수 있습니다. 그리고 누적합도 알아낼 수 있고, 이를 이용해 구간 합을 구할 수 있습니다.

구간 합이 $K$가 되는 경우의 수는 모르겠습니다. 두 포인터에다가 $ax + by = c$ 꼴의 정수 해 경우의 수 세는 방식으로 셀 수 있을 것 같습니다.

5. 철도

문제 요약

$1 \le n, m \le 8; n \times m \le 20$ 격자 위에서 $(1, 1)$에서 시작해 $(n, m)$까지 이동하는 경로의 개수.

단, 경로는 철도이다. 직선 형태, 90도 틀어진 형태, 십자로 교차하는 형태가 있을 수 있다. 격자위의 임의의 칸에 장애물이 있을 수 있다.

풀이

재방문을 허용하는 경로의 개수 세는 문제로 생각할 수 있습니다. 재방문하면 기존의 -나 | 모양의 철길이 + 모양으로 바뀝니다.