[백준 BOJ] 11726번 2*N 타일링 (C++/cpp)

문제 설명

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

 

 

접근 방법 - DP의 기초 응용문제 (점화식 설계)

백준의 11726번 문제는 DP(다이나믹 프로그래밍)의 기초 문제로 점화식 설계를 통해 해결할 수 있는 문제이다.

해당 문제는, 입력으로 주어지는 n에 대한 2*n 크기의 직사각형을  2*1, 1*2 타일을 통하여 채울 수 있는 가짓수를 구하여 출력해야 하는 문제이다.

이때 문제를 살펴보면, 도출된 결과에 대해 10,007로 나눈 나머지 값을 정답으로 출력해야 하니 해결할 시에 이 점을 참고하길 바란다.

 

필자는 우선 n=1부터 시작하여 몇 가지 입력에 대한 경우의 수를 직접 세어보았다.

2*1 크기인 경우 (n=1) => 1가지

2*2 크기인 경우 (n=2) => 2가지

2*3 크기인 경우 (n=3) => 3가지

2*4 크기인 경우 (n=4) => 5가지

위 내용을 요약하면 아래와 같다.

• (입력) 1 -> (결과) 1
• (입력) 2 -> (결과) 2
• (입력) 3 -> (결과) 3
• (입력) 4 -> (결과) 5

 

그리고 필자는 위를 통하여, 아래와 같은 하나의 점화식을 찾을 수 있었다.

result[n] = result[n-1] + result[n-2] (n>=3)

 

필자는 위 식을 기반으로 하여 코드를 작성하였고, 이를 통해 문제를 해결할 수 있었다.

보다 자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 함께 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 각각의 가짓수를 저장할 배열(memo)을 미리 선언해 둔다.

(입력의 최댓값이 1000인 점을 감안하여 배열의 크기를 설정해 두었다.)

 

2) 입력값이 1, 2인 경우엔 점화식을 적용할 수 없기 때문에, 연산을 수행하기 전에 초기값을 미리 임의로 설정해 둔다.

(위의 설명에 기재되어 있는 대로, memo[1]은 1로 memo[2]은 2로 설정한다.)

 

3) 값(n)을 입력받는다.

 

4) 반복문의 제어 변수 i값을 3부터 하여 n까지 증가시키면서, 아래의 연산을 수행한다.

- 현재 i에 대해, 위 설명의 점화식을 적용하여 배열의 원소값을 저장하도록 한다.

(최종 결괏값을 구하기 위해선 그 이전의 값들도 모두 필요하기 때문에, [1]부터 [n-1]까지의 배열값들을 순차적으로 구해보아야 한다.)

▶ 이때 문제에서 최종 결괏값에 10,007을 나눈 나머지를 정답으로 출력하라고 하였기 때문에, 그 이전의 배열값들에 대해서도 10,007 이상의 값은 필요 없다고 볼 수 있다. 따라서 점화식을 수행할 때마다 10,007을 나눈 나머지로 배열값을 저장하도록 한다.

 

5) 4)의 연산이 모두 끝났다면, 최종적으로 저장된 memo[n]을 정답으로 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 11726번 코드
int memo[1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	memo[1] = 1;
	memo[2] = 2;

	int n;
	cin >> n;

	for (int i = 3; i <= n; i++) {
		memo[i] = (memo[i - 1] + memo[i - 2])%10007;
	}
	cout << memo[n]<< endl;
}

 

제출 결과

(2022.09.16 백준 11726번 문제 제출 결과)