제2회 가톨릭대학교 프로그래밍 경진대회(CCPC)
백준20152 Game Addiction
일반성을 잃지 말고 $H \leq N$이라고 합시다. 오른쪽/아래로 가는 것이 최단 경로임을 알 수 있습니다.
단순 DP 문제입니다.
백준20153 영웅이는 뭐시기
최대한 많은 항으로 나타낸다는 것은, 이진법으로 분리한다는 이야기입니다.
단순 구현 문제입니다.
백준20154 이 구역의 승자는 누구야?!
단순 구현 문제입니다.
$N + N/2 + N/4 + N/8 + \ldots \leq 2N$이므로 $O(N)$에 문제를 풀 수 있습니다.
백준20155 우리 집 밑에 편의점이 있는데
지문이 이해하기 어렵게 쓰여있는데, 최빈값을 구하라는 이야기입니다.
단순 구현 문제입니다.
백준20156 기왕 이렇게 된 거 암기왕이 되어라
KOI 2016 중등부 3번 트리과 거의 똑같은 문제입니다. (풀이)
백준20157 화살을 쏘자!
사분면 별로 / 기울기 별로 풍선의 개수를 구하면 됩니다. 분수 꼴로 나타내는 것을 추천합니다.
백준20158 사장님 달려가고 있습니다
$D(i, j, d, c)$: 마지막에 가속도를 $c$만큼 받아서 $d$방향으로 이동했을 때, $(i, j)$로 가는 최소 시간
BFS 문제입니다.
백준20159 동작 그만. 밑장 빼기냐?
밑장 빼기를 하기 전에는 인덱스가 홀수인 카드를 가져가고, 이후에는 짝수인 카드를 가져갑니다.
Prefix Sum을 이용해, 밑장빼기를 하는 위치에 따른 $O(N)$가지 경우를 각각 $O(1)$에 계산하면 됩니다.
백준20160 야쿠르트 아줌마 야쿠르트 주세요
다익스트라
백준20161 왜 동전은 하나씩만 뒤집는 거야
$D(idx, bit)$: $idx-1$번째 동전까지는 원하는대로 완성시켰고, $[idx, idx+k-1]$번째 동전의 상태를 $bit$로 만드는 최소 횟수
로 정의하여 Bit DP를 돌리면 됩니다. DP를 사이클 없는 방향 그래프(DAG)로 생각해서 0-1 BFS나 다익스트라를 돌려도 됩니다.
백준20162 간식 파티
Weighted LIS를 구하는 문제입니다.
LIS를 세그먼트 트리로 구하는 것처럼 DP를 하면 됩니다.