다이나믹프로그래밍

생각의 방향 DP 알고리즘 개념을 처음 공부하고 스스로 푼 문제! 바텀업(Bottom-up) 방법으로 푸는데 성공했다. 가장 까다로운 점은 '점화식 찾기' 였다. 어떻게 풀어야할지 고민하다가, 일단 경우의 수를 직접 적어가며(머릿속으로 상상하고 그리며) 점화식을 도출해냈다. 🔻 메모장에 적어가며 알아낸 점화식 더보기 n=2 -> 2개 n=3 [가로] [가로] [가로] -> 1 [세로] [세로] [가로] [가로] [세로] [세로] -> 3개 (1(=dp[1])+2(=dp[2])) n=4 [][][][] [][][][] -> [가로][가로][가로][가로] (all 가로) -> 1 -> [세로][세로][세로][세로] (all 세로) -> 짝수일 때 가능 1 => 2값 dp[2] 랑 동일. (거의 /2) -> ..