[백준/C++] 11726번_2xn 타일링
문제는 다음과 같습니다.
저는 거의 모든 dp문제를 초항 구하기 그리고 점화식 세우기 이 두가지를 구한 후에 풉니다.
- n=1일때 a(1)=1
- n=2일때 a(2)=2
그리고 n번째 규칙은 다음과 같습니다.
타일을 마지막으로 붙인 경우를 확인해보면,
마지막 타일을 2x1 타일을 붙인 경우 => a(n-1)+ <2x1 타일>
마자막 타일을 1x2 타일을 두 개 붙인 경우 => a(n-2) + <2x2 타일 2개>
즉, 점화식은 다음과 같습니다.
a(n) = a(n-1) + 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)+func(num-2))%10007;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
a[1]=1;
a[2]=2;
int n;
cin>>n;
cout<<func(n)<<endl;
return 0;
}
2/5 토요일 복습)
오 복습할때에는 bottom-up 방식으로 풀었는데, 이 전에서는 top-down을 이용했네요.
복습때 푼 풀이는 다음과 같습니다.
#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]=2;
for(int i=3; i<=n; i++){
dp[i]=(dp[i-1]+dp[i-2])%10007;
}
cout<<dp[n]<<endl;
return 0;
}
Author And Source
이 문제에 관하여([백준/C++] 11726번_2xn 타일링), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ssssujini99/백준C-11726번2xn-타일링저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)