반응형
SMALL
타일 채우기 python
-
백준 2225번 합분해, 2133번 타일 채우기 (Python, DP)알고리즘 2023. 9. 7. 11:16
2225번 합분해 0~N개의 숫자 K개를 더해서 N을 만드는 경우의 수를 구하는 문제입니다. 덧셈의 순서가 바뀐 경우 다른 경우로 셉니다. 풀이 다이나믹 프로그래밍을 이용해 이전의 결과값들을 저장해서 다음에 사용할 수 있도록 했습니다. dp 배열의 행은 N을 나타내고 열은 K를 나타내도록 2차 배열로 선언했습니다. 1️⃣ N이 1인 경우 K에 상관 없이 dp[1][k]=k입니다. 1을 1개의 숫자로 만드는 방법은 1 1을 2개의 숫자로 만드는 방법은 0+1, 1+0 1을 3개의 숫자로 만드는 방법은 0+0+1, 0+1+0, 1+0+0 ... 이므로 dp[1][i]=i 입니다. 2️⃣ k가 2인 경우 N에 상관 없이 dp[n][k] = n+1 입니다. 1을 2개의 숫자로 만드는 방법은 0+1, 1+0 2를..