algorithm/dp

풀이 수열에서 n번째 중 몇 번째에 오는지 표시하는 열과, 1~9까지의 수를 나타내는 열로 2차원 배열 arr을 만든다. 그리고 배열에는 그 번째가 그 숫자로 끝날 때의 값을 넣는다. 가령 arr [2][3] 은 2번째 자리가 3으로 끝날 때의 계단 수이다. 계단 수의 규칙에 따라, 0으로 끝났다면 앞 수는 1이어야만 계단수이다. 1로 끝났다면 앞 수는 0이나 2여야만 계단수이다. 2로 끝났다면 이전수는 1이나 3이어야만 계단수이다. 3으로 끝났다면 이전수는 2나 4여야만 계단수이다. . . . 8로 끝났다면 이전수는 7이나 9이어야만 계단수이다. 9로 끝났다면 이전수는 8이어야만 계단수이다. 즉, arr [m][n]=arr [m-1][n+1]+arr [m-1][n-1]이다. (단, n이 0이면 arr ..

풀이 피라미드 형태의 문제 그대로 배열을 만들면 된다. n에는 높이, m에는 수평개수가 들어가는 arr [n][m] 배열을 만든다. n에는 높이, m에는 수평개수가 들어가는 dp[n][m] 배열도 만든다. dp [0][0]에 점화식을 위한 처음값 arr [0][0]을 넣어준다. 그리고 dp[n][m]에 dp [n-1][m]과 dp [n-1][m-1] 중 큰 값을 고르고 arr [n][m]을 더해 할당한다. 이때 인덱스가 최소 최대 범위를 넘지 않도록 조심한다. 그리고 마지막 dp[n]에서 배열들 중 최댓값을 출력한다. 해답 코드 #include #include #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace s..

풀이 문제를 해석해보자, 일렬로 된 집이 있다. 그런데 양 옆집과는 같은 색이면 안되며, 색을 칠하는 비용은 집마다 색깔마다 각기 다르다. 이때 최솟값을 구하라는 문제이다. 많은 경우의 수를 생각해야 한다. 색깔이 3개이니 [집의 수][3] 인 이차원 배열을 만든다. 그리고 각 dp[n][m]에는 n번째 집에 m번째 색깔을 칠했을 때 나올 수 있는 최솟값을 넣는다. dp[n][m]은 dp[n-1][m이 아닌 다른 값] 에 비용을 더하면 된다. 이전 입력된 배열들을 바탕으로 다이나믹 프로그래밍으로 풀면 된다. 하위 배열에서 입력된 값에 근거하기 때문이다. 해답 코드 #include #include #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(..

풀이 입력된 수열들을 arr []에 저장한다. 다이내믹 프로그래밍으로 dp [n]에 n번째 원소를 마지막으로 취할 때의 길이를 저장한다. 그리고 dp 배열에서 최댓값을 찾으면 된다. 그러면 dp[n]은 어떻게 찾을 수 있을까? 입력을 받을때마다, 이전 배열값들을 탐색한다. n> m일 때, arr [m]>n; int arr[n]; int dp[n]; cin>>arr[0]; dp[0]=1; for(int i=1; i>arr[i]; beforemax=0; for(int j=0; j

풀이 함수의 규칙에 따라 재귀함수로 출력해야 한다. 재귀함수로 출력하되, 이미 저장된 값은 동적계획법으로 바로 출력할 수 있게 하면 된다. 하지만, 이 문제에서는 재귀함수 말고 반복문을 통한 동적계획법으로도 출력이 가능해 재귀함수를 사용하지 않는 방식으로 풀었다. 비슷한 문제가 나올 경우, 재귀함수를 이용해 푸는 것을 추천한다. 해답 코드 #include #include #include #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int arr[101][101][101]; int main(){ int a=1,b=1,c=1; while(!(a==-1&&b==-1&&c==-1)){ cin>>a>>b>>..

풀이 이항계수 공식을 이용해야 한다. N과 K를 공식으로 쓰면 nCk = nC(k-1)+(n-1) C(k-1)가 나온다. 즉, 초깃값부터 다이나믹 프로그래밍으로 풀어야 한다. 단 여기서, 10007로 나눈 나머지를 원했으므로 숫자 범위 추가를 조심해야 한다. 해답 코드 #include #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main() { fastio; int dp[1001][1001]={0}; unsigned int n,r; cin>>n>>r; for(int i=1;i

풀이 입력되는 수열들을 arr [n]이라고 하자. 연속된 arr[n]의 합 중 가장 큰 것을 구해야 한다. 이를 위해 arr[n]을 보고 동적계획법으로 값을 결정하는 수열을 dp [n]이라고 하자. dp [n]은 arr [n]을 마지막 원소로 하는 최댓값이 되는 수열이다. 수열의 당장 다음값이 음수더라도 그 수열을 끊지 않고 이어갔을 때 절댓값이 더 큰 양수들을 얻을 수 있다면 수열을 이어나가야 한다. 그렇다면 어떻게 이것을 판단할 수 있을까? 일단 새로운 값이 나오면 음수더라도 더하되, 현재까지 dp[n]의 값이 음수라면 그냥 새로운 arr[n]값부터 새로 시작하면 된다. 이미 합이 음수가 되어버린 dp[n]은 더이상 답이 될 수 없다. 그냥 새로운 arr[n]부터 시작하면 된다. dp [n-1]에서 ..

풀이 새로 생겨나는 큰 삼각형들의 한 변의 길이는 이전 삼각형들의 두변의 길이의 합니다. 쭉 나열해보면 6번째는(흰색 3) = 5번째(파란색 2)+1번째(파란색 1) 7번째는(파란색 4)=6번째(흰색 3)+2번째(흰색 1) 8번째는(흰색 5)= 7번째(파란색 4)+3번째(파란색 1) 9번째는(파란색 7)=8번째(흰색 5)+4번째(흰색 2) 10번째는(흰색 9)=9번째(파란색 7)+5번째(파란색 2) 11번째는(파란색 12)=10번째(흰색 9)+6번째(흰색 3) 어떤 삼각형의 한편 길이는 바로 직전의 삼각형과 5번째 전의 삼각형 한변 길이의 합임을 알 수 있다. 따라서 n번째 삼각형의 한 변의 길이를 arr [n]이라고 할 때 arr [n]= arr [n-1]+arr [n-5]라고 할 수 있다. n-5부터..