[BOJ/백준] 1904번 - 01타일

단계별로 풀어보기 > 동적 계획법 1 > [3단계] 1904번

 

문제 링크 : https://www.acmicpc.net/problem/1904

 

문제 요약

1. 주어진 문제에 대한 규칙을 찾아 점화식을 세운다.

 

입력 복사

예제 입력 1 >> 출력 : 5

4

 

CODE

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mod 15746

const int mxN=1e7;

ll term[mxN+1];
ll dp(int n) {
	if(n==1) return 1;
	if(n==2) return 2;
	
	if(term[n]!=0) return term[n]%mod;
	
	else {
		term[n] = dp(n-1) + dp(n-2);
		return term[n]%mod;
	}
}

int main() {
	int n;
	cin >> n;
	
	cout << dp(n) << endl;
	
}

 

문제 풀이

1. 규칙을 찾아 점화식을 구한다.