[백준/C++] 11727번_2xn 타일링2
문제는 다음과 같습니다.
초항을 구하면 다음과 같습니다.
n=1, a[1]=1
n=2, a[2]=3
점화식의 규칙은 다음과 같습니다.
- 마지막 타일을 1x2 한 개를 붙인 경우 => a(n-1) + <1x2 타일 1개>
- 마지막 타일을 2x1 두 개를 붙인 경우 => a(n-2) + <2x1 타일 2개>
- 마지막 타일을 2x2 한 개를 붙인 경우 => a(n-2) + <2x2 타일 1개>
즉, 점화식은 다음과 같습니다.
a(n) = a(n-1) + 2*a(n-2) (단, n>=3)
전체 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int a[1001]={0, };
int func(int num){
if(a[num]) return a[num];
return a[num]=(func(num-1)+2*func(num-2))%10007;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
a[1]=1;
a[2]=3;
int n;
cin>>n;
cout<<func(n)<<endl;
return 0;
}
2/5 토 복습)
이번에 복습하면서 푼 풀이는 다음과 같습니다.
복습에서는 bottom-up 방식을 이용하여 풀었습니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int dp[1001]={0, }; int n; cin>>n;
dp[1]=1; dp[2]=3;
for(int i=3; i<=n; i++){
dp[i]=(dp[i-1]+(2*dp[i-2]))%10007;
}
cout<<dp[n]<<endl;
return 0;
}
Author And Source
이 문제에 관하여([백준/C++] 11727번_2xn 타일링2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ssssujini99/백준C-11727번2xn-타일링2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)