180519 동아리 연습 문제 풀이

A. 자두나무

난이도: 중등부 2번, 분류: DP

$dp[x][y]$를 다음과 같이 정의하자.

 

$dp[x][y]$ = 시간 x까지 y번만 이동해서 자두를 받아먹었을 때 최대로 받아먹을 수 있는 개수

 

이동한 횟수만으로 현재의 위치를 얻어낼 수 있다. 짝수 번 이동했으면 1, 홀수 번 이동했으면 2의 위치에 있을 것이다. 현재 위치를 $pos$라고 하자. 이렇게 정의하고 나면, 다음과 같은 점화식을 세울 수 있다.

 

$$dp[x][y] = \max ( dp[x-1][y-1], dp[x-1][y]) + (a[x] == pos)$$

 

이 값들을 모두 계산한 뒤, 각 y=0..k까지에 대해 dp[n-1][y]의 최댓값을 구하면 된다.

B. 수열의 합

 

난이도: 중등부 1번, 분류: 수학, 아이디어

다양한 풀이가 있을 수 있다. 이들 가운데 두 가지를 소개한다.

 

풀이 1. 주어진 수들을 모두 합치면 "전체 원소들의 합"의 $2(n-1)$배가 된다. 또, $i$번째 행의 모든 수들의 합은 원소들의 합 + $A_i \times (n-2)$가 된다. 이를 이용해서, 전체 원소들의 합 $S$를 구하면, $A_i$는 $i$번째 행의 원소들의 합에서 $S$를 빼고, $n-2$를 나누면 된다.

 

풀이 2. 1번째 행에서, $A_3 \cdots A_n$에서 $A_1$을 더한 수치를 알 수 있다. 2번째 행에서, $A_3 \cdots A_n$에서 $A_2$를 더한 수치를 알 수 있다. 1행 2열의 값은 $A_1 + A_2$이므로, 두 행의 $3 \cdots n$번째 원소를 더한 뒤, $A_1 + A_2$로 나누고 절반을 하면 $A_3 \cdots A_n$을 구할 수 있다. 이로부터 $A_1, A_2$는 쉽게 구할 수 있을 것이다.

 

한 가지 참고할 수 있는 것은, 문제에서 $2 \leq n$이라고 되어 있지만, 조건을 만족하는 수열이 유일함에서 $n=2$인 경우는 $[1, 1]$만이 가능하다. 특히 풀이 2의 경우에는 $n=2$인 경우가 예외 처리가 필요할 수도 있고, 이는 적절히 고려해 주도록 하자.

 

C. 랜선 자르기

 

난이도: 중등부 2번, 분류: 이진탐색

역으로, 길이가 L인 랜선을 최대로 많이 만들어야 한다고 해 보자. 이 때, 최대로 만들 수 있는 개수는 모든 주어진 간선의 길이를 L로 나눈 몫의 합이다. 이제, f(L) := 만들 수 있는 길이가 L인 랜선의 최대 개수 를 정의하자. f(L)은 감소함수가 되고, f(L)이 N 이상이 되는 최대의 L을 구하면 된다.

 

이는 이진 탐색으로 쉽게 해결하고, 다음과 같은 기본적인 로직을 사용하면 될 것이다.

 

L <- 작은 수, R <- 큰 수

While L+1 < R:

M = (L+R)/2

If (f(M) >= N): L = M

Else: R = M

 

위 코드는 $f(L) >= N$, $f(R) < N$의 두 불변 조건을 항상 만족하고, 따라서 답은 L이 된다.

 

D. 고속도로

 

난이도: 고등부 1번, 분류: DP

일단, 들어온 나들목의 번호 목록 $in$과 나간 나들목의 번호 목록 $out$을 정렬해 두자. "들어올 때 사용한 나들목과 나갈 때 사용하는 나들목이 달라야 한다"라는 조건만 없다면 모든 $i$에 대해 $in[i]$에서 $out[i]$로 나가는 것이 최적해일 것이다. 하지만 이 조건 때문에 고려할 것이 생긴다. 증명은 생략하지만, 최적의 방법은 다음 네 가지 중 하나이다.

 

1. $in[x] \rightarrow out[x]$
2. $in[x] \rightarrow out[x+1]$, $in[x+1] \rightarrow out[x]$
3. $in[x] \rightarrow out[x+1]$, $in[x+1] \rightarrow out[x+2]$, $in[x+2] \rightarrow out[x]$
4. $in[x] \rightarrow out[x+2]$, $in[x+1] \rightarrow out[x]$, $in[x+2] \rightarrow out[x+1]$

 

말로 풀어 말하면, 많아야 세 개의 번호 이내에서 순서를 섞으면 해결된다는 것이다. 이는 $dp[x]$를 $in[x]$와 $out[x]$까지 처리한 최적해라고 정의했을 때에, 네 개의 경우를 계산해 주면서 해결할 수 있다.

 

E. Hotels

 

난이도: 고등부 2번, 분류: 트리, 조합

호텔 A, B, C 세 개를 지었을 때에 A에서 B, C로 가는 경로를 생각해 보자. 두 경로는 A에서 출발한 뒤 몇 개의 "공통된 간선"을 따라 이동할 것이고, 어떤 "갈림길"이 있어서 B와 C로 도달할 것이다. "갈림길"이 시작하는 정점을 생각해 보면, 이 정점에서 A, B, C로 이르는 거리는 같아야 한다. 이런 정점 P는 무조건 존재하고, 각 호텔 배치에 대해 유일하다.

 

N의 제한이 그닥 크지 않으므로, N개의 각 정점에 대해 이 정점이 P인 경우에 경로를 세 주면 된다. 정점 P를 루트로 해서 트리를 세웠을 때에, 각 서브트리에 "P와의 거리가 $1, 2, …, N-1$인 정점의 개수"를 기록해 두면, 간단한 조합으로 "P의 서로 다른 서브트리에 속하면서 거리가 같은 정점들의 개수"를 구할 수 있다. 예를 들어, 각 서브트리에 대해 거리가 $k$인 정점의 개수가 $a_1 , …, a_r$개라고 하자. 그러면, 이 때 구하는 개수는 이 수열에서 서로 다른 세 개의 원소의 곱을 모두 합한 값이 된다. 이렇게 고른 세 정점 A, B, C는 각각 P와의 거리가 $k$가 되고, 서로 간의 거리는 $2k$가 된다.