본문 바로가기

백준/DP

 (67)
백준 2040 - 수 게임 https://www.acmicpc.net/problem/2040 이 문제는 대단히 교육적인 문제이므로 꼭 공부하는 것을 추천한다. 게임 전략 A와 B 둘 다 최적으로 플레이를 한다고 했다. 이를 수식으로 표현하면 어떻게 될까? A의 합을 $sum_{A}$, B의 합을 $sum_{B}$라고 하면 A와 B의 목표는 다음과 같이 정리할 수 있다. A는 $sum_{A} - sum_{B}$를 최소화시켜야 한다. B는 $sum_{A} - sum_{B}$를 최대화시켜야 한다. (혹은 $sum_{B} - sum_{A}$를 최소화시켜야 한다.) 그러면 저 값을 최적화 하는 문제로 표현할 수 있고 이는 동적 계획법으로 시도해볼 수 있을 것이다. 그런데 어떻게 동적 계획법을 해야 할까? 테이블을 다음과 같이 정의한다. d..
백준 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를 돌린다는 건 알겠는데 몇 번 하는가? 가 중요할 것이다. 어떤 특정한 횟수를 넘어서도 계속 이동할 수 있다면 게임을 무한으로 할 수 있다는 의미가 된다. 그러면 그 임계값을 정해야 하..
백준 14517 - 팰린드롬 개수 구하기 (Large) https://www.acmicpc.net/problem/14517 풀이 다음 테이블을 세운다. dp(i, j) := i번째 문자부터 j번째 문자까지 해서 부분 수열을 구성했을 때 나올 수 있는 팰린드롬의 갯수 그러면 dp(i, i) = 1, dp(i, i + 1) = 2로 초기화를 할 수 있다. 이 때 입력으로 주어진 문자열 s에 대해 s[i] = s[i + 1]이면 대칭인 팰린드롬이 존재하는 것이므로 dp(i, i + 1) = 3이 된다. 그리고 부분 수열이 가질 수 있는 범위 gap마다 반복문을 돌면서 다음을 더하거나 빼면 된다. 시작점이 i이고 끝점이 j일 때... dp(i + 1, j)에서 그대로 가져오는 경우 -> dp(i, j)에서 단순히 확장한 것으로 간주할 수 있다. dp(i, j - 1..
[ICPC] 백준 23342 - Histogram https://www.acmicpc.net/problem/23242 서론 대회 때 누적합을 쓰는 dp겠거니 싶어서 시도해봤는데 풀지 못하고 도망쳤었다. 이번에 다른 풀이를 참조했는데 아마 대회 중에는 떠올리지 못했을 것이다. 테이블 설계 이 문제를 dp로 푸는 테이블은 다음과 같다. dp(i, j) := i번째 인덱스에서 버킷이 j개 남았을 때 분산의 최솟값 탑 다운 dp로 풀 때는 0부터 시작하는 다른 함수와 달리 n부터 시작하면서 내려가는 방식이다. 분산 구하기 중고등학교 교과 과정을 무사히 이수 했다면 모집단에서 분산을 구하는 식은 다음과 같음을 잘 알고 있다. $\sum(X - m)^{2}$ 우리는 위 분산 계산을 고속으로 하기 위해 식을 일부 전개 후 누적합을 사용할 것이다. $\sum (X^{..

티스토리툴바