본문 바로가기

백준/DP

 (67)
백준 15678 - 연세워터파크 www.acmicpc.net/problem/15678 단조 큐를 이용해 최적해를 빠른 속도로 계산할 수 있는 동적계획법 문제이다. 동적계획법에 단조 큐를 활용하는 과정은 다음과 같다. 1. 먼저 덱에서 현재 징검다리로 건너올 수 없는 징검다리를 모두 제거한다. 2. 지역 최적해를 가진 이전 징검다리에서 현재 징검다리로 건너올 경우의 최적해를 계산한다. 현재 징검다리를 시작점으로 해서 가지는 점수나 이전 징검다리에서 가지고 있는 최적해 + 현재 징검다리를 밟았을 때 점수 둘 중 하나가 될 것이다. 3. 계산한 최적해와 최대 점수를 비교해서 저장한다. #덱에는 이동할 수 있는 범위의 징검다리만 있으므로 계산한 최적해는 최댓값이 아닌 극댓값이라는 사실에 유의한다. 4. 현재 계산한 최적해보다 작은 값을 가지고..
[KOI] 백준 2494 - 숫자 맞추기 www.acmicpc.net/problem/2494 동적계획법을 통해 현재 자물쇠의 상태를 저장하여 푸는 문제이다. 나사가 몇번 회전했는지도 구해야 하므로 dp 테이블 뿐만 아니라 역추적 테이블도 생성해야 한다. 각 테이블의 정의는 다음과 같다. dp 테이블 dp[i][j] := i번째 나사가 현재 상태에서 j번 왼쪽으로 회전한 상태일 때 원하는 숫자로 맞추기 위해 회전한 칸수의 최소 역추적 테이블 backward[i][j] := i번째 나사가 왼쪽으로 j번 회전한 상태일 때 최적해에 도달하기 위해 왼쪽으로 회전한 칸수 바텀 업 dp로 현재 나사에서 원하는 상태를 오른쪽으로 돌려서 맞췄을 때, 왼쪽으로 돌려서 맞췄을 때를 계산해준다. 회전 칸수는 모듈러 연산을 이용해 구해준다. 이 과정에서 최적해가 갱신..
백준 1514 - 자물쇠 www.acmicpc.net/problem/1514 기본 풀이는 dp이면서도 점화식 진행에 탐욕적 방법이 들어가는 어려운 문제이다.다음 상태로의 진행자물쇠의 왼쪽 디스크부터 오른쪽 방향으로 진행해 잠금을 푼다고 해보자. 그렇다면 첫 시작할 때 기준점은 0번 디스크이고 기준점에서 2번 디스크까지 고려를 해야 한다. 다음 기준점인 1번 디스크로 가기 위해선 0번 디스크가 무조건 알맞은 숫자에 맞춰져 있어야 하고 이는 탐욕적 속성을 만족해야 함을 알 수 있다. 그렇다면 다음 상태는 우선 기준 디스크가 맞춰진 상태에서 오른쪽으로 인접한 두 개의 디스크를 어떻게 회전시킬 것이냐에 따라 갈리게 된다. 기준 디스크를 x, 첫번째 인접 디스크를 y, 두번째 인접 디스크를 z라고 하고 설명하겠다. 1. x와 y, z를 ..
[COCI] 백준 10740 - ACM www.acmicpc.net/problem/10740 문제 소개 Zagreb 대학교에 속한 스테판, 이반, 구스타프가 모로코에서 열리는 ICPC WF를 참석한다. 그들의 전략 가이드 고란은 필승전략을 가져왔는데 그 전략은 다음과 같다. 대회 극초반에 각 멤버가 n문제의 난이도를 분석한다. (1부터 5까지 있으며 5가 제일 어렵다.) 그리고 각 팀원이 풀 문제를 연속적으로 분배한다. (1 2 3 4 5 번이 있으면 1 2 / 3 / 4 5 처럼 분배할 수 있다.) 어떤 사람이라도 문제를 풀지 않는 경우는 없어야 한다. 이렇게 문제를 분배할 때 각 팀원이 담당한 문제의 분석 난이도 합이 최소가 되는 분배 방법을 찾아야 한다. 풀이 - 탑 다운 dp 다음 이차원 dp 테이블을 생각해보자. dp[i][j] :=..
[ICPC] 백준 2135 - 문자열 압축하기 www.acmicpc.net/problem/2135 다음 dp테이블을 정의한다. dp[i][j] := i번째부터 j번째까지 부분 문자열을 압축한 길이 문자열을 얼마나 압축이 가능한지 파악하기 위해 문자열을 압축할 구간의 길이에 대해 반복문을 돌린다. 문자열을 압축할 수 있는 모든 경우를 탐색하기 위해 해당 길이의 진약수를 모두 구하여 저장한다. 이 진약수들에 대해 반복문을 돌려 구간 내 문자열들이 진약수를 길이로 가지는 부분 문자열들로 압축이 가능한지 확인한다. 예를 들어 길이가 8인 "gogogogo"를 압축한다고 하고 8의 진약수 중 2에 대해 계산하면 "gogogogo"에서 길이 2의 부분 문자열은 "go"가 되므로 부분 문자열로 압축할 수 있음을 확인할 수 있다. 만약 압축이 가능하면 부분 문자열..

티스토리툴바