11726번
-
[백준 9095번] 11726번 : 2xn 타일링 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 3. 30. 19:35
백준알고리즘 11726번 : 2xn 타일링 (Solved.ac 난이도 Gold5) 요약 : 피보나치 수열의 규칙이 있는 DP 문제 ↑클릭시 문제 link로 이동합니다.😊 이 문제는 Dynamic Program 알고리즘 중 Top-down 방식으로 풀어보았다. 큰 단위를 작은 단위의 문제로 쪼개서 풀어야하는데, 내가 적절하게 잘 쪼개는지를 검증하기위해 최소 단위를 내가 직접 풀어보았다. 2xN 의 면적을 1x2의 타일과, 2x1의 타일로 채울 수 있는 집합의 개수를 구하는 문제이다. 따지고보면 경우의 수를 구하는 문제인데, 2x3의 타일부터 규칙이 생길것으로 판단되니(타일의 최대길이가 2이므로) 2x1과 2x2의 경우의 수를 구하고, 2x3의 경우의수가 하위 갯수의 집합의 합이 되는 DP로 구성되는지 검증..