성인 게임 (BOJ 23256)

문제

이미지클릭

문제 설명

• 여기에서 n=1인 경우에는 2*2의 정사각형 하나이다.
• n=6인 경우에는 2*2 정사각형이 6개가 보이는 형태가 된다.

• 그리고 두 가지 조각이 존재하는 데 조각은 서로 회전 가능하다.

문제 해설

• 여기에서 제일 중요한 n=(i-1)를 활용하여서 n=i 인 개수를 체우는 것이다.
• 기본적으로 두개의 dp테이블을 활용하여서 결과를 도출하였다.

d1: 다음과 같은 형태의 개수를 저장해 줌

d2: 다음과 같은 형태의 개수를 저장해 줌

• 그렇다면 d1, d2는 어떻게 채워야 하는지 알아보자.

d1 [i]=d1 [i-1]*3+d2 [i-1]*4로 구할 수 있다.

d2 [i]=d2 [i-1]+d2 [i-1]*2로 구할 수 있다.

최종 코드

#include<bits/stdc++.h>
using namespace std;
const int MOD=1000000007;
vector<long long> d1(1000004,0),d2(1000004,0);
int main(){
      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
      d1[1]=7, d2[1]=3;
      for(int i=2;i<=1000000;i++) {
            d1[i]=(d1[i-1]*3+d2[i-1]*4)%MOD; #d1구하기
            d2[i]=(d1[i-1]+d2[i-1]*2)%MOD; #d2구하기
      }
      int t; cin>>t;
      while(t--){
            int x; cin>>x;
            cout<<d1[x]<<"\n";
      }
}

이미지클릭