본문 바로가기

백준/DP

 (63)
백준 1398 - 동전 문제 https://www.acmicpc.net/problem/1398 1398번: 동전 문제첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다.www.acmicpc.net 힌트 1더보기동전 교환 문제를 그리디 하게 풀려면 주어진 동전들의 값이 서로 서로소가 아니어야 함이 알려져 있다. 일단 적당한 범위 안에서의 답을 dp로 모두 구해놓고 dp로 도출한 해와 그리디로 푼 해의 차이를 비교해 보자. 유의미한 결과를 얻을 수 있는가?힌트 2더보기30, 40, 80, 90  해설더보기적당히 큰 범위 내에서 dp로 해를 찾은 뒤 그리디하게 구한 해와 비교해보자. 그러면 다..
백준 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..

티스토리툴바