하나씩 알아가기

문제를 해결하기 위한 점화식을 구하려면 2차원 dp를 만들어야 합니다. dp[n][1] = dp[n-1][2] + dp[n-1][3] dp[n][2] = dp[n-2][1] + dp[n-2][3] dp[n][3] = dp[n-3][1] + dp[n-3][2] n을 만들기 위한 방법의 수 중 1로 끝나는 경우를 dp[n][1]이라고 합시다. dp[n][1]은 ~~~ + 1 이런 식입니다. dp[n-1][?] 의 경우 1로 끝날 수 없기 때문에 2나 3이 올 수 밖에 없기 떄문에 dp[n][1] = dp[n-1][2] + dp[n-1][3]가 성립합니다. 그리고 dp[n][2]의 경우 주의해야 할 점은 ~~~ + 2로 끝났기 때문에 dp[n-2][?] 이 와야 한다는 점입니다. ※반복문 내부의 점화식에 %1..

정수 n을 입력 받아서, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다. 1, 2, 3이라는 숫자가 고정이 되어 있습니다. 규칙을 찾아봅시다. n 1 2 3 4 5 경우의 수 1 2 4 7 ? 네번째 까지 구한 결과 f(1) + f(2) + f(3) = f(4)가 성립합니다 다섯번째 까지만 수동으로 구해봅시다 11111 1112 1121 1211 2111 122 212 221 113 131 311 23 32 총 13가지입니다. f(2) + f(3) + f(4) = f(5) 가 성립하므로 f(n) = f(n-3) + f(n-2) + f(n-1) 로 점화식을 도출할 수 있습니다. dp = [0 for _ in range(11)] dp[1] = 1 dp[2] = 2 dp[3] = 4 fo..

점화식을 찾아봅시다. 그림을 보고 입력받은 수가 n이라 할 때, n-2번째 까지의 경우는 두 가지이고 n-1번째 까지의 경우는 한 가지입니다. 좀 더 자세히 말하면 n-2번째까지 타일이 채워진 경우에서 너비가 2인 블럭으로 채우면 n번째 항까지 채운 경우가 되고 n-1번째 까지 타일이 채워진 경우에서 너비가 1인 블럭으로 채우면 n번째 항까지 채운 경우가 되는 것입니다. 그래서 f(n) = 2 * f(n-2) + f(n-1) 이렇게 점화식을 구할 수 있습니다. n = int(input()) dp = [0 for _ in range(1001)] dp[0] = 0 dp[1] = 1 dp[2] = 3 for i in range(3, n+1): dp[i] = 2 * dp[i-2] + dp[i-1] print(d..

그림을 그려가면서 가로의 길이에 대해 몇 가지의 방법으로 타일링을 할 수 있는지 구해봅시다 가로의 길이 1 2 3 4 방법의 수 1 2 3 5 점화식이 피보나치 수열처럼 이루어지는 것을 알 수 있습니다. f(n) = f(n-2) + f(n-1) (n>2) 위의 테이블대로 dp테이블을 구현해준다는 생각으로 코드를 짜겠습니다. n = int(input()) dp = [0 for _ in range(1001)] dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = dp[i-2] + dp[i-1] print(dp[n]%10007); 조금만 잘못 짜면 IndexError가 발생할 수 있으니 주의해야합니다. 결과로 특정 수와 나눈 나머지를 출력하라고 요구하는 이유는 결과값이 ..