하나씩 알아가기

n = int(input()) dp = [0 for _ in range(91)] dp[1] = 1 dp[2] = 1 for i in range(3, n+1): dp[i] = dp[i-2] + dp[i-1] print(dp[n]) 0으로 시작하지 않으면서 11을 부분 문자열로 갖지 않는 수를 이친수라 합니다. 일단 낮은 차수의 항들을 수동으로 구해줍시다. 1 2 3 4 1 10 100 101 1000 1010 1001 첫번째 두번째 항을 주목해 보면 한자리 수 이친수에 01을 붙이고 두자리 수 이친수에 0을 붙이면 101, 100으로 세자리 수의 이친수가 되는 것을 발견할 수 있습니다. 두자리 수 이친수에다가 01을 붙이고 세자리 수 이친수에 0을 붙이면 1001, 1000, 1010으로 네자리 수의 이친..

문제를 해결하기 위한 점화식을 구하려면 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가 발생할 수 있으니 주의해야합니다. 결과로 특정 수와 나눈 나머지를 출력하라고 요구하는 이유는 결과값이 ..

10을 세 가지 연산을 이용하여 1로 만든다고 할 때 모든 경우 중에 가장 작은 수를 찾아내야 합니다. 10 -> 9 -> 8 -> 7 -> ... -> 1 (x) 10 -> 9 -> 3 -> 1 (o) * 점화식: 수열의 각각의 항들의 관계를 나타낸 식 모든 경우의 수를 고려할 경우 점화식을 떠올리는 방법을 생각해 내는 것이 좋은 방법이 될 수 있습니다. 이 문제의 경우 수를 줄일 수 있는 연산은 세 가지 밖에 없으므로 점화식은 이 경우를 포함하여 적어줘야 합니다. f(n) = 1 + min(f(n/3), f(n/2), f(n-1)) 그런데 가령, f(n/3)이 반드시 존재하는 값은 아닐 수 있지만 이렇게 점화식 형태로 표현이 가능한 경우 다이나믹 프로그래밍을 적용하여 문제를 해결하는 것이 가장 일반적..