11726
-
[DP] BOJ 11726 번 문제백준 문제풀이/Dynamic Programming 2019. 5. 11. 01:48
문제분석 내용이 어렵지 않아서 추가적인 설명은 굳이 필요 없을 것 같아서 패스할게요~ 저만 그럴 수도 있지만... 처음에 이 문제를 보고 생각한 게 배열의 행을 2로 잡고 해야 되나? 도형을 뭐로 표현하지? 라고 생각했었는데 그럴 필요가 없더군요... DP 문제 점화식만 파악하면 되는 문제입니다. 우선 눈으로만 봐도 알 수 있는 경우의 수를 정의해봅시다! D[n] = 가로길이가 n 인 직사각형을 채우는 경우의 수 A = 가로길이가 2 인 직사각형 B = 가로길이가 1 인 직사각형 이라고 했을 때, D[0] = 0 D[1] = 1 D[2] = 2 3가지 경우는 확실해집니다. 이제 D[3] 에 대해서 봅시다. 상황을 두 가지로 나누어 볼 수 있습니다. D[3] 의 처음 블록을 A 로 시작하는 경우 이 경우 ..