백준 11726번 (2×n 타일링, C++, DP) [BAEKJOON]

2×n 타일링

https://www.acmicpc.net/problem/11726

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초256 MB129015491373625835.942%

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

출처

알고리즘 분류


접근 방법

N =1 부터 나올 수 있는 경우를 체크했다.

그림을 그리면서 확인해본 결과

N = 3이라면 N = 1과 N = 2가 합쳐진 경우다.

통과된 코드

#include <iostream>

using namespace std;

constexpr int MOD = 10007;
					
long long int arr[1001];

int main()
{
	// Tabulation: Bottom Up 방식

	long long int N = 0;

	cin >> N;

	arr[1] = 1, arr[2] = 2;

	for (int  i = 3; i <= N; i++) {
		arr[i] = ( arr[i - 1] % MOD + arr[i - 2] % MOD) % MOD;
	}

	cout << arr[N];

	return 0;
}

틀린 이유는 모듈러 연산에서 괄호를 잘못 묶었다.

테스트 케이스 통과해서 좋다고 제출 했는데 틀렸다고 해서 당황

테스트 케이스는 나머지 연산이 의미가 없어서 결과가 잘나오니…

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

Scroll to Top