전체 글 (277) 썸네일형 리스트형 백준 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,.. 앳코더 민트 후기, 민트 가는 법 (앳코더 공부법) 1300 정도 되면 해당 색깔에 안착했다 판단하고 글을 쓰려고 했는데 대박이 터져서 지금 쓰게 되었다. 왜 써요? 인터넷에 검색하면 코드포스 블루 가는 법은 인기가 많은데 앳코더 민트 가는 법은 글 자체가 없어서 쓴다. 앳코더 민트도 충분히 가기 어렵다... 여기 통계에 따르면 앳코더 민트는 코드포스 블루와 동동하다고 여긴다. 그래서 앳코더를 널리 추천하고 싶기도 하고 나처럼 코드포스가 아니라 앳코더를 목표로 공부하는 사람들에게 도움이 되라는 뜻으로 부족하지만 글을 쓴다. 물론 코포 퍼플이나 앳코더 블루 이상이신 분들은 코웃음 치면서 넘기면 된다. 민트를 어떻게 달았는가? 사실 본인은 민트를 허무하게 찍었다. AtCoder Beginner Contest 258을 보면 등수가 418로 확 튄 것을 볼 수 .. 백준 1103 - 게임 https://www.acmicpc.net/problem/1103 이 포스트에서는 다소 무식한 방법을 사용한다. 일단 동적 계획법을 수행할 건데 테이블에서 상태는 "해당 위치를 갈 수 있는가?"로 정의하며 각 이동을 계산해 현재 테이블에서 다음 테이블로 바꾸는 방법을 사용할 것이다. 그러면 각 위치에서 상태가 1일 때(처음에는 (0, 0)만 1이다.) 주어진 조건에 따라갈 수 있는 좌표를 모두 1로 갱신하면 될 것이다. 물론 기존 테이블에다 갱신하는 게 아니라 다음에 쓸 테이블에다 해야 한다. 그러면 위치를 갱신하는 dp를 돌린다는 건 알겠는데 몇 번 하는가? 가 중요할 것이다. 어떤 특정한 횟수를 넘어서도 계속 이동할 수 있다면 게임을 무한으로 할 수 있다는 의미가 된다. 그러면 그 임계값을 정해야 하.. 이전 1 2 3 4 5 6 7 8 ··· 56 다음
