본문 바로가기
728x90

백준브실골/DP45

백준 10978, 기숙사 재배정 개요 문제 링크 골드 2, DP p[i] != i이도록 permutation 구성하기 접근 수능 경우의 수에서도 종종 보이는 문제, 수능에서는 수형도를 그리라고 지시한다. 노가다를 하라는 의미. 하지만 DP를 이용하면 논리적으로 문제를 해결해줄 수 있다. 아래 예시를 보자. // n = 5 ABCDE B???? ABCDE의 첫 자리에는 A가 오면 안되고, BCDE가 올 수 있는데, 첫 자리 수를 제외한 나머지 수의 구성은 (같은,다른)이 (3,1)로 동일하므로 B가 앞자리에 오는 경우 × 4를 해주면 된다. 즉 f(5) = (3,1) × 4 그럼 위 예시의 정답을 구해보자. ABCDE BA??? -> (3,0) = f(3) (2,1) (BC??? BD??? BE???) BCA?? -> f(2) BCD??.. 2023. 2. 19.
백준 13707, 합분해 2 개요 문제 링크 골드 4, DP N을 K개의 수의 합으로 나타내는 방법의 수 접근 조합론으로 풀 수도 있을텐데, DP는 Knapsack 생각하면 될 것 같다. 일단 N=5000이니까 O(N^3)은 안된다. 그럼 knapsack을 어떻게 O(N^2) 안에 해결하냐? 개념적으로 접근해보자. N을 K개로 만드려면, [0,N]을 K-1개로 만든 경우를 모두 더해주면 된다. 그럼 2차원 dp를 활용해야 하나? 아니다. 굳이 쓰지 않고 1차원 dp 두개를 이용해 복붙해주면 된다. 그럼 K번 돌리면서, N에 대해, n보다 작은 수의 k-1경우를 모두 더해주는 과정이다. 우선 for문 3개로 구현을 해보자. for (K) for (N) for (i = 0~n) sum += dp[i][k-1] dp[n][k] = sum.. 2023. 2. 17.
백준 5569, 출근 경로 개요 문제 링크 골드 4, DP 두 칸 이상 이동후 방향 전환을 하며 이동하는 경로의 수 접근 경로탐색 문제 중 생각할 여지를 많이 주는 좋은 문제이다. 2차원 dp를 사용하는데 두 가지 조건을 생각하면 되는 문제. 조건을 어기는 상황을 생각하자. 번개모양이 생기면 되는데, 이걸 dp로 어떻게 푸냐? 경로 탐색 dp의 근본부터 다시 생각해야 한다. dp[y][x] = dp[y][x-1]+dp[y-1][x] 보통의 경로탐색 dp는 이렇다. 왼쪽과 아래쪽의 경로 수를 더해준다. 그런데 여기서는 이를 잘 응용해 이렇게 바꾸면 문제가 해결된다. dp[y][x].from_left = dp[y][x-1].from_left + dp[y-1][x-1].from_down dp[y][x].from_down = dp[y-1.. 2023. 2. 17.
백준 22968, 균형 개요 문제 링크 골드 5, DP 왼쪽, 오른쪽의 subtree의 높이차가 1 이하인 binary tree의 최대 높이 접근 재귀적 성질을 잘 활용하면 되는 문제, 난 AVL tree가 뭔지 모른다. 그만큼 몰라도 충분히 풀 수 있다. 높이가 k인 트리를 생각하자. 이 트리의 높이가 균형을 이루려면 왼쪽, 오른쪽 subtree가 균형을 이루어야 한다. 그런데 그리디하게 생각해서, 가장 높은 트리를 만들려면 왼쪽과 오른쪽 트리의 높이가 1차이 나는 것이 좋다. 왼쪽이 높다고 가정하면, 높이가 k인 트리의 왼쪽 subtree는 k-1 균형트리, 오른쪽 subtree는 k-2균형 트리가 된다. 이제 dp를 사용해보자. dp[k]를 높이가 k인 트리를 만드는데에 필요한 최소 정점수 라고 하자. 그럼 왼쪽에는 k-.. 2023. 2. 17.
백준 17856, Just Passing Through 개요 문제 링크 골드 4, DP 왼쪽 오른쪽보다 크고, 위아래보다 작은 지점을 n번 지나면서 가로로 이동하는 비용의 최솟값 접근 문제풀이보다 번역이 더 까다로운 문제. 2차원 경로탐색 dp인데 n번 지난다 라는 변수가 있으므로 3차원 dp를 이용해야 한다. 2차원 경로탐색 -> 골5, 3차원 -> 랭크+1 로 골4로 책정한듯. 우선 비용부터 생각하자. 비용은 왼위, 왼, 왼아래중 최솟값을 더하면 된다. 어떤 지점에 도달하기 위해서는 저렇게 세 가지 이전 점을 가지기 때문이다. 그리고 pass조건이 조금 까다로운데, 만약 어떤 (x,y)가 pass에 속한다면 이전점에서 n-1개의 pass를 지나온 비용과 비교해 업데이트 한다. 그렇지 않다면 n개의 pass를 지나온 비용과 업데이트한다. 왜냐하면 그 점을 .. 2023. 2. 17.
백준 1663, XYZ 문자열 개요 문제 링크 골드 1, DP 매 단계 X->YZ, Y->Z, Z->X로 변형이 일어날 때 전체 길이 / 문자 개수 / k번째 문자 구하기 접근 규칙성을 찾으면 크게 어렵지 않다. 우선 X,Y,Z의 개수를 생각해보자. X는 Z에서 온다. Y는 X에서 온다. Z는 X,Y에서 온다. 온다는게 뭔 말이냐 하니, 변화의 이전단계를 생각해보자. 변화를 역으로 취해보면 알 수 있다. 따라서 X[i] = Z[i-1], Y[i] = X[i-1], Z[i] = X[i-1]+Y[i-1] 이게 성립한다. 문자열의 길이는 X[i]+Y[i]+Z[i]이니까 따로 생각할 필요는 없다. 어려운 부분은 K번째 문자 구하기이다. 문제를 잘 들여다보면 s[n]+s[n+1] = s[n+3]임을 알 수 있다. 왜냐? X는 세 번의 시행 뒤.. 2023. 2. 17.
백준 13910, 개업 개요 문제 링크 골드 5, DP 최대 2개의 바구니를 사용해 물건을 옮기는 최소 횟수 접근 최대 2개까지만 사용가능하다. 문제 잘못읽었다가 메모이제이션 + 재귀로 꽤나 고생했다. dp에 들어갈 값은 n개 작업을 완료하는데에 필요한 최소 세트 수, 세트란? 1개 또는 2개를 사용하는 횟수를 말한다. 예를 들어, // n = 5, m = {1,3} 5 = {1,3}+{1} 2개의 세트를 사용하였다. 웍은 두개까지 사용가능하므로 n개 작업을 완료하려면 n-w[i] 혹은 n-w[i]-w[j]에서 +1을 한 값의 최솟값만큼의 세트가 필요할 것이다. 따라서 업데이트는 dp[n-w[i]]+1, dp[n-w[i]-w[j]]+1과 비교해 해주면 된다. Pseudo code dp[n] = minimum_set for (i.. 2023. 2. 17.
백준 5549, 행성 탐사 개요 문제 링크 골드 5, 누적합, DP 2차원 구간 내에 존재하는 문자의 개수 구하기 접근 2차원 경로탐색 DP와 매우 유사하다. 누적합이라도 결국 인접한 원소를 이용하는 것은 동일해서 DP로 분류했다. 우선 기본적인 누적합. 만약 1차원 배열에서 i부터 j까지 누적합을 구한다면 어떻게 할까? sum[1,j] - sum[1,i-1]을 해주면 된다. 동일하게 2차원에서 [y1,x1]부터 [y2,x2]까지의 누적합을 구한다면 sum[y2,x2]-sum[y2,x1-1]-sum[y1-1,x2]+sum[y1-1,x1-1]을 해주면 된다. 전체 합-왼쪽까지 합-위까지 합+왼쪽위까지 합을 해주는 것인데, 벤다이어그램을 생각하면 쉽다. 만약 A∪B를 구한다면 A+B-A∩B를 해줘야 한다. 어떤 C가 A,B를 포함한다.. 2023. 2. 17.
백준 14238, 출근 기록 개요 문제 링크 골드 3, DP, Greedy 1칸, 2칸, 3칸마다 존재 가능한 A,B,C를 이용한 문자열 구성 접근 분류는 DP인데 Greedy로 풀 수 있을 것 같아서 시도해봤음. 계속 1%컷나서 재귀쓰는 DP로 시도해봄, 또 1%컷 나서 결국 질문게시판을 둘러보다가 메모이제이션하고 백트래킹 이용한 풀이가 내 풀이랑 너무 다른 것을 확인했다. 다른 사람 풀이 읽는 것은 최소한으로 하려 했는데 달라도 너무 달라서 읽고 이해했음. Greedy 풀이는 조건 하나가 빠져있어서 틀린 거였음. Greedy 풀이도 다른 사람 풀이 읽으면서 이해했다. 아직 골3 풀 때가 아닌가... 정해는 메모이제이션 & 백트래킹인 것 같아 DP부터 알아보자. 1) DP 재귀문을 이용해서 풀이를 짜다보면 a,b,c의 개수를 입력.. 2023. 2. 12.
백준 27210, 신을 모시는 사당 개요 문제 링크 골드 5, DP 1과 2로 이루어진 수열의 연속 부분수열의 1,2 개수차이의 최댓값 접근 저장할 값이 바로 생각나지는 않는 좋은 DP문제, 개수 차이의 최댓값을 구한다? 하면 dp에 저장할 값은 개수차이의 최댓값이겠구나. 그럼 이걸 어떻게 갱신을 해야 하나? 1차원 dp는 사용해서 안되고 2차원 dp를 사용해야겠음. 이유는? 1과 2에 대해 따로 값을 구해줘야 함. 따로 한다는 게 무엇을 따로 해야할까? 하고 생각하다가 아하, 1이 많은 배열과 2가 많은 배열을 구분하면 되겠구나 싶었음. 갱신은 어떻게? a[i]=1일때 1이 많은 배열의 길이는 +1해주면 되고, 2가 많은 배열은 -1을 해주면 되는데 음수는 없으니까 양수만 가져오면 됨. 말 대신 아래 예시를 보자. 편의상 1이 많은 배열.. 2023. 2. 12.
728x90

티스토리툴바