프로그래밍 연습장

180519 동아리 연습 문제 풀이 본문

문제 해결

180519 동아리 연습 문제 풀이

김준원 2018. 5. 19. 11:35


난이도: 중등부 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$ 된다.


'문제 해결' 카테고리의 다른 글

ICPC Yokohama Regional 2018  (2) 2020.07.20
190720 팀 연습: BAPC 2018  (2) 2019.07.21
180519 동아리 연습 문제 풀이  (0) 2018.05.19
180428 동아리 연습 문제 풀이  (1) 2018.04.28
180421 동아리 연습 문제 풀이  (1) 2018.04.21
180324 동아리 연습 문제 풀이  (0) 2018.03.24
0 Comments
댓글쓰기 폼