티스토리 뷰

반응형

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

 

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net


⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

  • 다이나믹 프로그래밍

 


 

⊙ 문제 접근 과정

 

DP문제를 보면 점화식을 세울 생각이 먼저 든다.

 

arr[N-1] + arr[N-2]일 때 두 가지로 나누어 푼다.


 

⊙ 문제 풀이

 

#include <iostream>

using namespace std;

int N;
int arr[1001];

int main() {
    cin >> N;

    arr[1] =1;
    arr[2] =2;
    for (auto i=3;i<=N;i++)
        arr[i] = (arr[i-2] + arr[i-1]) %10007;

    cout << arr[N];
}

 


⊙ 결과

 


⊙ 마무리

 

 

NONE

 

좋아요 로그인하지 않아도 누를 수 있습니다!

728x90
반응형
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
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
29 30 31
글 보관함