요즘은 새로운 DP 방법을 찾다보면 알아야 할 것이 많아 DP 문제 풀이를 정리해서 올려보고자 합니다.
겨울에 부지런히 DP를 파고 4~5시간을 들여 어려운 문제를 풀었는데 3월에는 3문제를 풀었나? DP Solving을 녹음하고 싶습니다.
어려운 백준(혹은 전골) 문제와 제가 생각해낸 간단한 풀이는 나중에 보기 편하도록 모아두었고, 아이디어나 그런 것들은 따로 따로 올리도록 하겠습니다.
난이도는 Gold 레벨에서 Pla 및 Diamond까지 탐색됩니다.
DP 외에 탐욕이나 데이터 구조에 대한 일기를 쓰고 싶은데 때가 왔습니다.
겨울에 해결하기 어려운 문제
#2647: 흑백 점 연결
2n개의 점이 x축의 좌표 1,2,…2n에 있습니다.
이 중 n은 검은색 점이고 n은 흰색 점입니다.
검정색 점과 흰색 점을 연결하여 쌍을 이루면 총 n개의 쌍이 형성됩니다.
몇 가지 포인트
www.acmicpc.net
꽤 어려웠습니다.
얼핏 욕심쟁이 같지만 dp로 쓰고 최적화된 경우를 역추적해야 하기 때문에 정말 오랫동안 붙들고 있었던 것 같다.
내 솔루션은 dp(i)(j)를 i에서 j까지의 최소 거리로 설정하고 dp가 최대일 때 높이를 h 배열로 설정하고 둘을 함께 회전시키는 것입니다.
역추적을 위한 역추적 배열도 설정했습니다.
지금 보면 코드가 좀 더럽습니다.
for (int mid = start; mid < start + t; mid++) {
tempdp(mid - start) = dp(start)(mid) + dp(mid + 1)(start + t);
if (!
(tempdp(mid - start))) tempdp(mid - start) = 1e4;
temph(mid - start) = large(h(start)(mid), h(mid + 1)(start + t));
if (!
(temph(mid - start))) temph(mid - start) = 1e4;
}여기서도 무심코 INF를 1e9에 넣었다가 더하면 오버플로(;;)되어 최대값을 예측해서 1e4정도로 낮춘 기억이 납니다.
여러모로 어려웠다.
또 다른 겨울 문제
2449호：전구
첫 번째 입력 라인에는 전구의 수를 나타내는 양의 정수인 N과 전구가 표현할 수 있는 색상의 수인 K가 포함됩니다.
단, N은 1 이상 200 이하의 정수이고, K는 1 이상 20 이하의 정수이다.
두 번째 줄은 N입니다.
www.acmicpc.net
1번 전구의 색상을 탐욕스럽게 커스터마이즈할 수 있다고 가정하여 문제를 해결한 것 같습니다.
1월에 풀었는지 기억이 안나니 다음으로 넘어갑시다.
최신 새로운 무료 플레 DP
1509: 회문의 나눗셈
세준이는 특정 사슬을 회문으로 나누고자 합니다.
예를 들어 ABACABA를 회문으로 나누면 {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA} 등이 있습니다.
최소 분할 수 출력
www.acmicpc.net
dp(i)(j)를 i에서 j까지의 나눗셈 수로 삼아 회문을 구분하면 시간복잡도가 O(N^3)이 되어 타임아웃이 발생한다고 생각했습니다.
그래서 안 풀고 며칠 지나니 회문이니까 1차원 dp만으로도 풀 수 있을 것 같았어요. 그것이 i에서 온 것인지 확인할 필요가 없다면, 중간에 있으면 어쨌든 전체 회문이 범위 내에 있지 않으면 회문으로 간주되지 않습니다.
따라서 dp(n)을 1에서 n까지의 나눗셈 수로 설정하고 뒤에서부터의 길이가 회문인지 확인하십시오. 내가 가서 할 수 있을까 따라서 k에서 n까지의 문자열이 회문이면 dp(n) = dp(nk) + 1이고 min(dp(n-1) + 1, dp(nk) + 1)로 일반화되면 시간 복잡도는 O( N^2) 시간 내에 해결할 수 있습니다.