본문 바로가기

백준

 (223)
백준 17353 - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 https://www.acmicpc.net/problem/17353 사전 지식 imos법을 알면 풀이를 쉽게 이해할 수 있다. 이 포스트에서는 imos법을 알고 있다는 가정 하에 설명하도록 한다. 공차가 1인 등차 수열 이 문제는 공차가 1인 등차수열을 구간에 더하면서 포인트 쿼리를 수행한다. 여기서 포인트 쿼리를 구간 쿼리로 바꿔보자. 점 x에 떨어진 별의 개수가 아닌 구간 [1, x]의 합을 구하는 쿼리로 바꾼다. 왜 이렇게 쿼리를 바꾸냐면 쿼리 1을 스위핑 덧셈 문제로 바꾸기 위함이다. 얘를 들어 다음 배열을 살펴보자. 1 2 3 4 5 이 배열의 원소들 $a_{1}, a_{2},... $을 $imos(i) - imos(0)$의 형태로 구하려면 어떻게 할까? 1 1 1 1 1 -5 이렇게 배열을 구..
백준 18287 - 체스판 이동 https://www.acmicpc.net/problem/18287 규칙 살펴보기 홀수 행와 짝수 행일 때의 이동은 그림으로 나타내면 다음과 같다. 문제에 아래로 가는 것만 가능하다 했으므로 다른 이동은 무시한다. 그러면 우리는 이 이동을 표현한 전이 행렬을 구상할 수 있다. MATRIX[i][j] := 현재 행의 i열에서 다음 행의 j열로 가는 경우의 수 그러면 $M^{2}$ 크기의 전이 행렬 두 개를 만들 수 있다. 이동 합성 행렬을 만든 건 좋은데 이 따로국밥인 행렬들을 어떻게 처리할지 난감하다. 이럴 때는 그냥 홀수 행 전이 행렬과 짝수 행 전이 행렬을 곱해 2번 이동하는 행렬을 만들면 된다. 그러면 우리는 2칸씩 이동하는 행렬을 표현했으므로 남은건 행렬 거듭제곱을 통해 이동 횟수 계산을 $O(M..
[ICPC] 백준 9341 - ZZ https://www.acmicpc.net/problem/9341 조건 정리 일단 문제를 편하게 풀기 위해 ZZ(0, 0)을 정의할 필요가 있다. $ZZ(0, 0) = b - a$로 둔다.(피보나치수열을 생각한다.) 직접 해보기 10 * 10 테이블을 단순한 dp로 출력해보자. 그러면 다음 발견을 할 수 있다. 어떤 항은 위처럼 Z 모양으로 더한 결과와 같다. 수식으로 나타내면 다음과 같다. $ZZ(a, b) = [\sum\limits_{i = 0}^{a}ZZ(i, b - 1)] + ZZ(0, b - 2)$ 그러면 우리는 위 식의 전개를 행렬로 표현할 수 있다. 예를 들어 c가 2인 경우 아래처럼 된다. $\left[ \begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\..
백준 24457 - 카페인 중독 https://www.acmicpc.net/problem/24457 아이디어 카페인이 낮은 걸 먼저 먹어야 한다. 왜냐하면 카페인이 작은 걸 먹어야 나중에 먹을 에너지 드링크의 손실을 최소화할 수 있기 때문이다. 그러면 카페인의 오름차순으로 정렬한 다음 동적 계획법으로 최적의 음료 선택을 계산해볼 수 있다. DP 테이블은 다음으로 둔다. dp(i, j) := i번째 음료를 먹을지 말지 결정하고 i번째부터 j개의 음료를 더 뽑을 수 있을 때 최대 지속시간 미래 카페인을 미리 계산하기 테이블을 짠 건 좋은데 카페인이 누적된만큼 효능이 손실된다는 조건을 고려해야 한다. 위에 테이블을 생각하면 j개의 음료를 뽑을 것이라고 고정한 상태기 때문에 우리는 누적 카페인 양을 미리 계산할 수 있다. 예를 들어 음료 1,..
백준 1103 - 게임 https://www.acmicpc.net/problem/1103 이 포스트에서는 다소 무식한 방법을 사용한다. 일단 동적 계획법을 수행할 건데 테이블에서 상태는 "해당 위치를 갈 수 있는가?"로 정의하며 각 이동을 계산해 현재 테이블에서 다음 테이블로 바꾸는 방법을 사용할 것이다. 그러면 각 위치에서 상태가 1일 때(처음에는 (0, 0)만 1이다.) 주어진 조건에 따라갈 수 있는 좌표를 모두 1로 갱신하면 될 것이다. 물론 기존 테이블에다 갱신하는 게 아니라 다음에 쓸 테이블에다 해야 한다. 그러면 위치를 갱신하는 dp를 돌린다는 건 알겠는데 몇 번 하는가? 가 중요할 것이다. 어떤 특정한 횟수를 넘어서도 계속 이동할 수 있다면 게임을 무한으로 할 수 있다는 의미가 된다. 그러면 그 임계값을 정해야 하..

티스토리툴바