본문 바로가기

Dynamic Programming

 (53)
백준 32250 - Super Shy (Easy) https://www.acmicpc.net/problem/32250힌트 1더보기만약 먼저 앉은 사람이 아무도 없을 경우 아무 자리에나 앉을 수 있다. 이 조건이 대단히 중요하다.힌트 2더보기최초로 사람을 배치한 이후, 규칙에 따라 사람을 배치하는데 나타나는 성질을 찾을 수 있는가?풀이더보기먼저 사람을 아무 곳에 배치한다고 해보자. 그러면 그 사람을 기준으로 나눈 왼쪽 구간과 오른쪽 구간 $L$과 $R$을 얻을 수 있다. $L$과 $R$에서 사람을 배치할 때는 문제의 규칙에 의해 다음과 같은 성질을 발견할 수 있다. 구간 $L, R$에서 첫 번째 사람이 놓인 기준점을 포함하여 각 사람과의 거리는 2 또는 3이다. 이는 거리를 가능한한 멀리 떨어트려야 한다는 조건을 만족시키기 위해 중앙에 배치하면서 다시 두..
백준 1398 - 동전 문제 https://www.acmicpc.net/problem/1398 1398번: 동전 문제첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다.www.acmicpc.net 힌트 1더보기동전 교환 문제를 그리디 하게 풀려면 주어진 동전들의 값이 서로 서로소가 아니어야 함이 알려져 있다. 일단 적당한 범위 안에서의 답을 dp로 모두 구해놓고 dp로 도출한 해와 그리디로 푼 해의 차이를 비교해 보자. 유의미한 결과를 얻을 수 있는가?힌트 2더보기30, 40, 80, 90  해설더보기적당히 큰 범위 내에서 dp로 해를 찾은 뒤 그리디하게 구한 해와 비교해보자. 그러면 다음 사실을 발견할 수 있다. 해당 문제의 답을 $f(x)..
백준 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..
[KOI] 백준 2507 - 공주 구하기 https://www.acmicpc.net/problem/2507 발상 단순히 가는 경우면 어렵지 않게 계산할 수 있겠는데 구출하고 돌아와야 한다. 다음과 같은 생각을 해볼 수 있다. 갔다가 돌아오는 게 아니라 그냥 2명의 사람이 밟는 발판을 겹치지 않게 이동하기 이렇게 두면 테이블이 dp[501][501]인 dp 테이블을 구상할 수 있다. 위처럼 테이블을 두면 다음과 같은 점화식을 생각해볼 수 있다. f(i, j) := 공주를 구하기 위해 i번째 돌을 밟았고 도망치기 위해 j번째 돌을 밟는 경우의 수(거꾸로) 각각 i와 j에 대해 갈 수 있는 발판을 탐색하면서 경우의 수를 더하는 탑 다운 dp를 고려할 수 있다. 유의 사항 다만 이렇게 동적 계획법을 수행하면 주의해야 할 사항이 있다. 1. j는 목적지..

티스토리툴바