본문 바로가기

DP

BOJ 24231 해석 https://www.acmicpc.net/problem/24231 24231번: 해석 $($와 $)$로만 이루어진 문자열을 괄호 문자열이라고 한다. 괄호 문자열 중, 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 한다. 빈 문자열은 올바른 괄호 문자열이다. $A$가 올바른 괄 www.acmicpc.net 컨디션 난조로 3주만에 처음으로 문제를 풀어봤다. 어떠한 암호 문자열이 주어졌을 때, 이 암호 문자열을 분해하는 방법은 아래의 두 가지 방법이 있다 AB - A와 B모두 올바른 암호 문자열. 대응 가능한 괄호 문자열 -> (...)(...) xAy - A는 올바른 암호 문자열, x와 y는 서로 다른 암호 문자. 대응 가능한 괄호 문자열 ((..)) 주어진 문자열을 부분 문자열로 분해하여 각각 문.. 더보기
BOJ 6171 땅따먹기 (볼록껍질 최적화) https://www.acmicpc.net/problem/6171 6171번: 땅따먹기 (1) / (4) / (2, 3) 으로 땅을 묶어 사보자. 상헌이는 100 * 1 + 20 * 15 + 1 * 100 = 500의 가격에 땅을 살 수 있다. www.acmicpc.net 볼록껍질 최적화가 일감 이었으나 쉽게 점화식을 유도하지는 못했다. 우선 두 개의 땅 a, b에 대해서 W_a >= W_b 이고 H_a >= H_b 이면, 땅 b는 땅 a와 한 묶음으로 사는게 무조건 이득이다(추가 비용이 발생하지 않는다). 전처리를 해서 b와 같은 땅을 모두 걸러낸 뒤, 너비에 대해서 오름차순으로 정렬을 하면 높이는 내림차순으로 정렬이 된다. 너비에 대해 정렬이된 세 개의 땅 a, b, c를 생각해보자. 이때 (a, c.. 더보기
BOJ 12766 지사 배정 (분할정복 동적계획법 최적화) https://www.acmicpc.net/problem/12766 12766번: 지사 배정 입력의 첫줄은 4개의 정수 n, b, s, 그리고 r로 이루어진다. n (2 ≤ n ≤ 5 000)은 교차로의 개수, b (1 ≤ b ≤ n − 1)는 지사의 수, s (1 ≤ s ≤ b)는 하위 프로젝트의 수, r (1 ≤ r ≤ 50 000)은 도로의 수를 www.acmicpc.net 방향그래프의 정점에 위치한 그래프들을 S개의 그룹으로 묶어, 한 그룹내에서 모든 지사들 사이에서 통신을 할 때, 총 통신비용을 최적화 하는 문제이다. 두 지사 사이의 통신은 항상 본부를 거쳐서 지나가야 한다. 따라서 본부 s에서 지사 u까지의 거리 D[s][u], 그리고 지사 u에서 본부 s까지의 거리를 D[u][s] 라고 하면.. 더보기
BOJ 5466 상인 (IOI 2009 Salesman) https://www.acmicpc.net/problem/5466 5466번: 상인 어떤 상인이 육지에서 최적 여행 스케줄을 구하는 것이 매우 어려웠기 때문에, 직선으로 흐르는 다뉴브강을 따라 이동하면서 물건을 팔기로 했다. 이 상인은 다뉴브 강을 따라 임의의 위치로부 www.acmicpc.net 문제 분석 단계에서 아래의 성질을 이용할 수 있지 않을까를 고민하다 결국 더 오래 걸린 문제 상인은 결국 시작점으로 돌아와야 한다. 따라서 올라간 거리의 합 = 내려간 거리의 합. DP 식을 잘 조작을 해서 컨벡스 홀 최적화나, 크누스 최적화를 적용하기. 위의 조건을 잊어버리고 그냥 각 경우 별 DP 점화식을 생각해 보면, 우선 시장들을 시장이 열리는 날짜 순으로 정렬을 한 뒤, DP[i] = i 번째 시장을 .. 더보기
BOJ 13261 탈옥 (분할정복 동적계획법 최적화) https://www.acmicpc.net/problem/13261 13261번: 탈옥 한 간수가 1, 2, 3번 방을, 다른 간수가 4, 5번 방을, 다른 간수가 6번 방을 감시한다고 하면 탈옥 위험도가 최소가 된다. 1, 2, 3번 방을 감시하는 간수는 총 3명의 죄수를 감시하고 있기 때문에, 1, 2, www.acmicpc.net 컨벡스 홀 최적화 각인줄 알고 식 유도하려고 뻘짓하다가 알고 보니 너무 당연하게 분할정복 최적화였던 문제. 분할정복 최적화를 적용할 수 있는 케이스는 아래와 같다. 점화식: DP[i][j] = min { DP[i-1][k] + C[k][j] } ( k < j ) C[k][j] 는 monge array C[a][c] + C[b][d] 더보기
Tight words http://acm.pku.edu.cn/JudgeOnline/problem?id=2537 Description Given is an alphabet {0, 1, ... , k}, 0 더보기
Cake Cutting Description You are given a rectangular cake of integral dimensions w × h. Your goal is to divide this cake into m rectangular pieces of integral dimensions such that the area of the largest piece is minimal. Each cut must be a straight line parallel to one of the sides of the original cake and must divide a piece of cake into two new pieces of positive area. Note that since a cut divides only a.. 더보기
Tri Tiling http://acm.pku.edu.cn/JudgeOnline/problem?id=2663 Description In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle. Input Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 더보기
TopCoder SRM 420 http://www.topcoder.com/stat?c=round_overview&er=5&rd=13511 한국시간으로 10월 2일 오후 8시에 SRM420이 열렸다. 개인적으로 SRM 417 이후로 3주만에 참가하는 SRM이기도 하고 ACM-ICPC예선을 제외하곤 최근 알고리즘 문제풀이를 거의 한적이 없어 약간 긴장이 되었지만 크게 부담갖지 않고 했던것 같다. 한국인이 이렇게 많이 참가한 SRM은 개인적으로 처음!! 250 - SolitaireSimulation Problem Statement Consider the following solitaire game: We have a deck of identical cards. Initially, these cards are split into severa.. 더보기
Risk http://acm.pku.edu.cn/JudgeOnline/problem?id=1603 Description Risk is a board game in which several opposing players attempt to conquer the world. The gameboard consists of a world map broken up into hypothetical countries. During a player's turn, armies stationed in one country are only allowed to attack only countries with which they share a common border. Upon conquest of that country, the ar.. 더보기

티스토리툴바