백준 - 11726
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
풀이
코드
#include <iostream>
using namespace std;
long long dp[1001];
int main()
{
int n;
scanf("%d", &n);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
dp[i] %= 10007;
}
cout << dp[n] << endl;
return 0;
}
#include <iostream>
using namespace std;
long long dp[1001];
int main()
{
int n;
scanf("%d", &n);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
dp[i] %= 10007;
}
cout << dp[n] << endl;
return 0;
}
처음엔 dp 배열에서 i가 홀수이면 i-1 배열에서 +1을 해주고, 짝수이면 i/2열에 * 2를 해준 후 +1을 해주면 되는줄 알았는데 틀렸다고 나왔다.
그래서 구글링해본 결과 dp[i-1] + dp[i-2]을 해주면 된다고 하는데...
처음엔 이해가 안갔다.
그림을 그려서 보니 이해가 됬는데
[i-1]일 때는 오른쪽 부분 마무리가 세로로 되는 것이고, [i-2]일 때는 오른쪽이 가로로 채워지며 마무리가 된다. 이렇게 자동적으로 마무리가 되기 때문에 [i-1] + [i-2]라는 점화식이 세워진다.
Author And Source
이 문제에 관하여(백준 - 11726), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsmmay322/백준-11726저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)