2xN 타일링2 11727: 2Xn 타일링 2 이 문제도 타일링 1문제와 같이 점화식만 찾으면 쉽게 풀 수 있다. dp[i-2]에서와 dp[i-1]에서 각각 길이가 2개짜리와 1개짜리를 더했을때 나오는 경우의 수를 구하여 점화식을 만들어보면 dp[i]=dp[i-1]+dp[i-2]+dp[i-2]가 된다. 점화식을 풀 때 dp[1]부터 하나하나 해보면서 구하는 것도 좋지만 dp[i]일때부터 생각해서 일반적인 해의 풀이를 구하는 것이 이 문제에서는 점화식을 더 찾기 쉬운 경우이다. i-1 덩어리와 i-2 덩어리가 있을 때 i짜리 덩어리를 만들기 위한 경우의 수를 구하면 된다. #include int dp[1001]; int main(void) { int n; scanf("%d",&n); dp[1]=1; dp[2]=3; dp[3]=dp[1]*dp[2]+dp.. 2023. 7. 29. [C] 11726: 2Xn 타일링 생각보다 쉽게 풀려서 깜짝 놀랐다 아무래도 평소에 조금 더 어려운 문제를 푸느라 상대적으로 쉽게 느껴졌나보다! 아무래도 점화식도 피보나치 수열과 같은 형태라 생각이 떠올리기 쉬웠고 점화식형태도 하나라서 직관적으로 보였다. 무엇보다 구현도 간단했는데 다만 주위해야할건 입력값이 1000개인데 피보나치 수열의 특성상 f(1000)은 int의 범위에서 벗어난다. 아마 long long int를 써도 벗어날 것 이다, 따라서 이때 생각났던 문제가 nCr, 조합 관련 문제였는데 이것도 n!이 n이 커질수록 기하급수적으로 커지기 때문에 n-i를 곱할때 i만큼 동시에 나눠져야 범위를 벗어나지 않는다. 이것도 마찬가지로 10007을 넘어갈 때마다 10007로 나눈 나머지를 dp[]에 넣어주면 된다. 다음은 아래 소스코드.. 2023. 7. 25. 이전 1 다음