[코드포스 - 1] 927 Div.3 A, B, D 풀이

A. Thorns and Coins

그리디적으로 접근하는 문제입니다.

왼쪽부터 차례대로 $1$칸 혹은 $2$칸을 움직일 수 있으며, 가시가 있는 곳으로의 이동은 불가능하다고 할때,

$i$번째 칸까지 먹은 코인의 개수를 $S_{i}$라고 하고, $i$번째 칸에 코인이 있으면 $A_i = 1$ 아니라면 $0$이라고 간주합시다.

그렇다면, 위 전제하에선 $S_{i-1} + A_i \geq S_{i-1}$이 성립합니다.

위의 식은 $A_i \geq 0$이기 때문에 항상 성립합니다.

 

그렇다면 언제 $2$칸을 뛰어 넘어야 하느냐를 결정해야 합니다.

따라서, $S_{i-2} + A_i \geq S_{i-2} + A_{i-1} + A_i$일때 뛰어넘는것이 최적입니다.

식을 정리해보면, $A_{i-1} \leq 0$일때만 가능한 건데, $1 \geq A_{i-1} \geq 0$입니다. 

따라서 성립하지 않습니다.

 

즉, 앞에 가시가 있을때에만 $2$칸을 뛰어넘는게 최적입니다.

(가시가 없고 바로 앞칸이 빈칸이어도 성립하나, 구현이 복잡해집니다.)

 

B. Chaya Calendar

수학 문제입니다.

$i$번째 신호가 발생할때까지 기다린 연도의 수를 $x$, $i+1$번째 신호에 있는 연도수를 $A_{i+1}$이라고 하면, $x \leq t; \ \ t \leq A_{i+1} \times k$를 만족하는 가장 큰 $t$를 계속 찾아나가야 합니다. ($k$는 0보다 크거나 같은 정수)

 

이때, 다음이 성립합니다.

$$\displaystyle \frac{t}{A_{i+1}} \leq k$$

따라서, 좌변에 있는 값을 이용해 $k$를 구하고, $t \geq A_{i+1} \times k$라면 $k$를 $1$ 증가시키면 됩니다.

 

D. Card Game

그리디적으로 접근하는 문제입니다.

'C', 'D', 'H', 'S' 중에서 조커카드 취급을 받는 그룹을 하나 고르면, 문제 상에선 다음이 성립합니다.

1. 조커그룹에 속한 카드는 다른 그룹에 있는 카드를 적힌 수에 상관없이 무조건 이긴다.
2. 조커그룹이 아닌 각 그룹에 속한 카드는, 수가 큰 카드가 수가 작은 카드를 이긴다.
3. 각각 한명씩 카드를 까면 두 카드를 버린다.

두 조건을 만족하면서 한번에 2장의 카드를 없애면서 모두 없애는 최적의 방법을 고안해야합니다.

그렇다면, 다음과 같이 접근할 수 있습니다.

1. 조커그룹이 아닌 각 그룹에 속한 카드는, 내림차순으로  정렬해서 큰거, 그 바로 다음 것을 뽑는다.
2. 조커그룹이 아닌 각 그룹에 속한 카드가 1을 따랐음에도 남는다면, 조커그룹에 있는 카드를 이용해 모두 제거한다.
3. 1, 2를 따랐음에도 카드가 남는다면 조커그룹 내에서 내림차순으로 정렬해서 큰거, 그 바로 다음 것을 뽑는다.

를 구현해주면 됩니다.