티스토리 뷰
요즘 새로운 DP 방법들 찾아보면서 뭔가 알아야 되는거도 많아지고 해서 정리도 할겸 DP문제 푸는걸 정리해서 올려보고 싶었다. 겨울에 열심히 DP 파면서 어려운 문제도 4~5시간씩 써가며 풀었는데 3월되서는 3개는 풀었나? 싶어서 DP 푸는걸 기록해볼거다. 난이도 있는 백준(또는 정올)문제랑 내가 생각했던 간단한 풀이를 같이 남겨 나중에 보기도 편하게 하고, 아이디어랑 이런건 따로 더 쓸거다. 난이도는 한 골드 상위에서 플래, 다이아까지 공부할거다. 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[n-k]+1 으로 하면 되고, 일반화해서 min(dp[n-1]+1, dp[n-k]+1)로 하니 시간복잡도가 O(N^2)이어서 시간안에 풀렸다.
'코딩일지' 카테고리의 다른 글
| 9월 일지 (0) | 2023.09.30 |
|---|---|
| 백준 그리디 일지 (3) (0) | 2023.04.29 |
| 백준 DP 일지 2 (0) | 2023.04.20 |
| 백준 그리디 일지 (2) - 순열 사이클 분할 (0) | 2023.04.05 |
| 백준 그리디 일지 (1) (1) | 2023.03.31 |