2020 경북대학교 Goricon
백준20112 사토르 마방진
단순 구현 문제입니다.
백준20113 긴급 회의
단순 구현 문제입니다.
백준20114 미아 노트
단순 구현 문제입니다.
백준20115 에너지 드링크
드링크 하나는 온전히 가져가고, 나머지는 절반만 가져갑니다.
가장 양이 많은 드링크를 온전히 가져가는 것이 이득입니다.
백준20116 상자의 균형
단순 구현 문제입니다.
백준20117 호반우 상인의 이상한 품질 계산법
(1번째로 작은 것, 1번째로 큰 것)
(2번째로 작은 것, 2번째로 큰 것)
(i번째로 작은 것, i번째로 큰 것)
을 묶으면 됩니다.
백준20118 호반우가 길을 건넌 이유
각 격자를 2번씩 이용하면 됩니다.
$1, 2, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6, …$ 같은 느낌으로 이동하면 됩니다.
백준20119 클레어와 물약
BFS를 위상정렬하는 느낌으로 돌리면 됩니다.
이때 정점의 Degree를 관리하는 것이 아니라, 어떤 레시피를 조합하기 위해 완성시켜야 하는 다른 레시피의 개수를 관리합니다.
백준20120 호반우와 리듬게임
$D(i, j, k)$: i번째 노트를 칠 때 누적 콤보가 j이고, 연속으로 미스를 k번한 경우
로 정의해서 DP를 하면 됩니다.
N이 3 이상이라면 미스 3번을 연속으로 낼 수 있기 때문에 최댓값은 항상 0 이상입니다.
백준20121 카드 셔플
0-based입니다.
X-셔플을 하면 $i$번째에 있는 카드가 $2i \mod N$번째로 갑니다.
Y-셔플을 하면 $i$번째에 있는 카드가 $2i+1 \mod N$번째로 갑니다.
$a$번째 카드가 $K$번의 셔플을 거쳐서 갈 수 있는 곳의 범위는 $[a\times 2^K, (a+1)\times 2^K)$입니다. 30 이하의 모든 $K$에 대해 테스트를 해봅시다.
셔플의 최소 횟수를 $x$라고 합시다. mod연산을 없애면, 적당한 $t$에 대해 $a$에서 $Nt + b$로 이동할 수 있다는 것을 의미합니다.
$a\times 2^K$와 $Nt + b$의 거리 $(Nt+b) - (a\times 2^K)$를 $d$라고 합시다. 셔플 순서는 $d$를 이진법으로 변환했을 때 0과 1을 각각 X, Y로 바꾼 것이 됩니다.
적당한 $t$는 이분 탐색을 통해 찾을 수 있습니다.
백준20122 중2병 호반우
$mn(i, j), mx(i, j)$: 열/행 방향으로 레이저를 쏜 상태를 비트로 나타낸 것이 각각 i/j일 때, 호반우가 얻을 수 있는 최소/최대 점수
로 정의하고 Bit DP를 하면 됩니다.
백준20123 L-트로미노 계단
$N$층짜리 계단을 만들기 위해서는 $N(N+1)/2$칸이 필요하고, 이 수는 3의 배수가 되어야 합니다.
그러므로 N을 3으로 나눈 나머지가 1이라면 불가능합니다.
N이 2면 가능, 3이면 불가능합니다.
N이 5면 불가능, 6이면 가능합니다.
N이 8이면 가능, 9면 가능합니다.
N이 10 이상인 경우에는 N으로 나눈 나머지가 1이 아니면 항상 가능합니다.
N을 3으로 나눈 나머지가 0인 경우, 위에 (크기 6인 계단), 가운데 (높이 N-6, 너비 6인 직사각형), 오른쪽에 (크기 N-6인 계단)을 배치하면 됩니다.
N을 3으로 나눈 나머지가 2인 경우, 위에 (크기가 N-2인 계단), 가운데 (높이 2, 너비 N-2인 직사각형), 오른쪽에 (크기 2인 계단)을 배치하면 됩니다.
재귀적으로 코드를 작성하면 됩니다.