안녕하세요 이번 시간에는 DP 문제의 유형을 분석해보는 시간을 갖도록 하겠습니다. DP 문제는 공통적으로 문제의 패턴을 더 작은 공통적인 패턴으로 나눌 수 있어야 하며 패턴들이 반복된다는 특징이 있습니다.
첫 번째 유형은 특정 수열의 N항을 구하는 문제입니다. 실제 수열이 주어지거나 혹은 리스트나 배열이 주어지고 N번째 수열을 구하는 문제이며, 특히 완전 탐색으로 풀 때 시간 초과가 발생하는 경우 사용합니다.
백준 9461(파도반 수열) 문제의 경우 파도반 수열의 N항을 구하는 문제입니다. 파도반 수열의 특징을 잘 살펴보시면 현재 값이 2개 이전의 값과 3개 이전의 값의 합으로 이루어져있다는 것을 알 수 있습니다. 즉 dp[i] = dp[i-2] + dp[i-3] 이라는 점화식을 가지고 dp[1] = 1, dp[2] = 1, dp[3] = 1 로 설정하여 dp[N]을 구하면 됩니다.
백준 1003(피보나치 함수) 문제의 경우 피보나치 함수 호출 시 0과 1이 각각 몇 번 출력되는지를 구하는 문제입니다. 이 문제는 0이 출력되는 횟수, 1이 출력되는 횟수를 각각 dp[i][j]로 설정하여
dp[i][0] = dp[i-1][0] + dp[i-2][0]
dp[0][0] = 1, dp[1][0] = 0
dp[i][1] = dp[i-1][1] + dp[i-2][1]
dp[0][1] = 0, dp[1][1] = 1
로 설정하여 풀 수 있습니다.
다음은 단순한 수열 문제가 아닌 응용 문제들입니다.
백준 2775(부녀회장이 될테야) 문제의 경우 a층의 b호에 살려면 자신의 아래층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와야 한다고 할 때 k층 n호에 몇 명이 사는지를 구하는 문제입니다. 문제를 그대로 해석하여 dp[i][j] : i층의 j호에 살고 있는 사람 수로 설정한 후 dp[i][j] = sigma(dp[i-1][k]), (k=1~j)로 설정하여 문제를 풀 수 있습니다.
백준 9623(BABBA) 문제의 경우 화면의 모든 B는 BA로 바뀌고 A는 B로 바뀔 때 버튼을 K번 눌렀을 때 화면의 A와 B의 개수를 구하는 문제입니다. 피보나치 함수 문제와 유사하게 dp[i][j] : 버튼을 i번 눌렀을 때 화면의 A와 B 개수로 설정한 후
dp[i][0] = dp[i-1][1]
dp[i][1] = dp[i-1][0] + dp[i-1][1]
로 점화식을 설정할 수 있습니다. 이 때 버튼을 한 번 눌렀을 때는 B만 존재하므로 dp[1][0] = 0, dp[1][1] = 1로 초기값을 설정해줍니다.
백준 1256(사전) 문제의 경우 N개의 a와 M개의 z가 있을 때 K번째 문자열을 찾는 문제입니다. 이 문제는 점화식을 세우는 것이 까다로운 문제인데, 문자열이 사전순으로 정렬되어 있기 때문에 문자열의 인덱스를 알면 문자를 구할 수 있다는 점에 포인트를 맞춰 dp[i][j] : a가 i개이고 z가 j개인 문자열의 개수로 설정해줍니다. 이후 a가 i개이고 z가 j개인 문자열은 a가 하나 없는 문자열의 개수에 a만 추가하면 되고 z가 하나 없는 문자열에 z만 추가하면 되기 때문에 각각의 dp의 합, 즉 dp[i][j] = Math.min(dp[i-1][j] + dp[i][j-1], K의 최대 범위)로 설정해줍니다. 이 때 두 합이 K 범위를 초과할 수 있기 때문에 초과할 경우 K의 최대 범위를 리턴합니다. 이 후 현재 문자열의 개수를 줄여나가면서 알파벳을 추가하면 되는데, a가 하나 없는 문자열의 개수보다 k가 크다면, 현재 문자열은 찾고자 하는 문자열의 위치보다 앞에 있다는 뜻이므로 z를 추가해서 문자의 순서를 뒤로 미뤄야 합니다. 이 때 k와 a가 하나 없는 문자 개수와의 차로 새로운 k로 넘겨주어야 문자가 추가된 나머지 문자를 기준으로 판단할 수 있습니다. 반대의 경우 a를 추가해주고, 만약 둘 중의 하나라도 0인 값이 있다면 나머지 값이 0이 될때까지 해당 알파벳을 추가합니다. 예를 들어 a가 3개 있고 z가 0개라면 현재 문자열에 a를 3번 연속 추가하면 됩니다.
