kthng

boj 11049 : 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 divide&conquer와 메모이제이션을 이용하여 해결하였다.a[i][1] : i번째 행렬의 row, a[i][2] : j번째 행렬의 col.위와같이 두면, 1. f(i,j) : i번째 행렬에서 j번째 행렬까지의 최소 곱셈 수2. f(i,j) = min { f(i,i) + f(i + 1,j) + a[i][1]*a[i+1][1]*a[j][2] , f(i,i+1) + f(i+2,j) + a[i][1]*a[i+2][1] + a[i][1]*a[i+2][1]*a[j][2], ... , f(i,j-1) + f(j,j) + a[i][1]*a[j][1]*a[j][2] } 중복된 연산을 제거하기 위해 f(i,j)를..

boj 2011 : 암호코드 https://www.acmicpc.net/problem/2011 a[i] : i번쨰 숫자c[i][1] : i번째를 1개로 인식할 때의 경우의 수.c[i][2] : i번째를 2번째 숫자로 인식할 때의 경우의수위와 같이 두면,1. c[i][1] = c[i][2] + c[i][1] (a[i] 는 0이 아닐 때)2. c[i][2] = (a[i - 1] == '1' || a[i - 1] == '2' && a[i]

boj 1520 : 내리막 길 https://www.acmicpc.net/problem/1520 메모이제이션을 적용한 재귀함수로 문제를 해결할 수 있다. 1. f(1,1) = 12. f(i,j) = f(i,j - 1) + f(i, j + 1) + f(i - 1,j) + f(i + 1,j) 만약 세준이가 평지도 이동하였다면 재귀에 loop가 생겨 이 방법으로는 불가능하다.세준이가 내리막길로만 이동하기 때문에 가능하다.