백준 (206) 썸네일형 리스트형 [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를 돌린다는 건 알겠는데 몇 번 하는가? 가 중요할 것이다. 어떤 특정한 횟수를 넘어서도 계속 이동할 수 있다면 게임을 무한으로 할 수 있다는 의미가 된다. 그러면 그 임계값을 정해야 하.. [ICPC] 백준 14961 - Untangling Chain https://www.acmicpc.net/problem/14961 관찰 같은 방향으로 가는 경우가 없다. 무조건 회전한다. 어쩌면 이를 이용해서 무언가 할 수 있을지도 않을까? 예제 tc 2번을 그려보자. 이처럼 겹치는 부분이 한 번 발생한다. 이를 해결하려면 어떻게 해야 할까? 가장 명확한 방법은 위에서 2만큼 이동하는 부분을 4로 조정하면 된다. 이를 유심히 보자. 밑으로 내려가기 전엔 왼쪽 방향으로 이동을 했었다. 밑으로 내려갈 때 교차가 일어나지 않으려면 왼쪽으로 이동할 때 충분히 이동해야 한다. 얼마만큼? 방문했었던 좌표 중에 가장 작은 x 좌표보다 1 이상 더 이동해야 한다. 이를 일반화 해보자. 이번에 아래 방향으로 이동을 한 상태라면 다음 이동은 왼쪽 또는 오른쪽으로 할 수밖에 없다. 그.. 백준 2016 국민대학교 교내 경시대회 풀이 https://www.acmicpc.net/category/detail/1541 2016 국민대학교 교내 경시대회 www.acmicpc.net 그렇다. 현재는 에디토리얼이 제공되고 있지 않으므로 후배로써 풀이를 복원하면 좋을 거 같아 글을 쓴다. PA 13410 거꾸로 구구단 시키는 대로 구구단을 수행하면서 뒤집은 수의 최댓값을 구하면 된다. CPP에서는 std::to_string으로 구구단 결과를 문자열로 바꾼 후 std::reverse로 뒤집고 다시 std::stoi로 전환하는 방법이 있다. 파이썬에서는 역시 str()로 문자열로 바꾼 후 슬라이싱 문법으로 뒤집은 다음 int()로 전환할 수 있다. std 함수의 경우 상수 시간이 크지만 문제에선 제한이 작으므로 문제없이 돌아간다. 전체 코드 - CP.. 이전 1 2 3 4 5 ··· 42 다음
