kthng

boj 1915 : 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 2가지 방법으로 풀었다.첫번째 방법은 sum을 이용하여 해결하는 것.sum[i][j]를 sum{ a[u][v] } (u는 1~i까지, v는 1~j까지)sum[i][j] - sum[i-k+1][j] - sum[i][j-k+1] + sum[i-k+1][j-k+1] == k*k 일때 한변의 길이가 k인 정사각형이다. 아래의 사진을 보면 참고가 될지도 모르겠다. 하지만 위의 방법은 아슬아슬하게 시간초과를 면한다. 시간복잡도는 n*m*min(n,m)이다. 두번째 풀이법은 다른사람들의 코드를 보고 나서야 떠올릴 수 있었는데, c[i][j]를 i,j를 오른쪽 아래로 둘 때의 가장 큰 정사각형이라고 생각하자. 그러면..

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]