Be myself :: [baekjoon 11727] 2*n타일링2

달력

022018  이전 다음

  •  
  •  
  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  •  
  •  
  •  

간단하게 상태dp로 풀어줍니다.

n일 때, 하나의 칸의 상태는 총 4가지 입니다.  1) 비어있는 경우 , 2) 위에 칸이 채워진 경우 3) 아래 칸이 채워진 경우 4) 모두 채워진 경우

규칙을 찾으면 다음과 같습니다. (n일떄 n-1은 모두 채워야 합니다. 왜냐하면 사용 가능한 타일이 2*1, 2*2 뿐이기 때문에 n-1을 모두 채우지 않으면 n+1에서 채울 수가 없습니다.)

위와 같이 규칙을 찾을 수 있습니다. 위를 토대로 코드를 짜면 다음과 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int dp[1001][4] = { 0, };
int main()
{
	int N;
	scanf("%d", &N);
	dp[1][0] = 1;
	dp[1][1] = 1;
	dp[1][2] = 1;
	dp[1][3] = 1;
	
	for (int i = 2; i <= N; i++)
	{
		dp[i][0] = dp[i - 1][3] % 10007;
		dp[i][1] = dp[i - 1][2] % 10007;
		dp[i][2] = dp[i - 1][1] % 10007;
		dp[i][3] = ((dp[i - 1][0] * 2) % 10007 + dp[i - 1][3]) % 10007;
	}

	printf("%d\n", dp[N][3] % 10007);
	return 0;
}

'Algorithm' 카테고리의 다른 글

[sw expert]모의sw역량테스트 보호필름  (0) 2017.10.09
[baekjoon 1500]최대 곱  (0) 2017.09.28
[baekjoon 11057]오르막 수  (0) 2017.08.12
[baekjoon 11727] 2*n타일링2  (0) 2017.08.11
Posted by flack3r