«   2022/06   »
      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    
Archives
Today
47
Total
86,237
관리 메뉴

차근차근

[백준 11727] 2×n 타일링 2 본문

대학교/Algorithm

[백준 11727] 2×n 타일링 2

SWKo 2020. 1. 20. 16:55

0. 제목

  • 백준 11726 2xn 타일링 2
  • BOJ 11726 2xn 타일링 2
  • C++ 2xn 타일링 2

1. 문제

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


2. 풀이

  • DP 방식을 이용하였다.
  • 초기값 2개(dp[1], dp[2])를 먼저 설정하고 가로의 길이가 1씩 증가할 때 어떻게 변할지 생각해보았다.
  • 가로의 길이가 1 증가했을 때 dp[i]라고 놓으면 1칸이 남았을때 채우는 방법 dp[i-1] 과 2칸이 남았을때 채우는 방법(2x2타일로 채우는 방법, 1x2타일 2개로 채우는 방법) 2xdp[i-2] 의 합으로 구할 수 있다. 따라서, dp[i] = dp[i-1] + 2*dp[i-2] 로 정리할 수 있다.
  • 반복문을 다 돌고 10007로 나누려면 수가 너무 커지기 때문에 dp[i]를 구할때 마다 10007로 나눈 나머지를 구해준다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int n;
    int dp[1001];
    
    cin >> n;
    dp[1= 1;
    dp[2= 3;
    for(int i = 3; i <= n; i++){
        dp[i] = (dp[i-1+ 2*dp[i-2]) % 10007;
    }
    cout << dp[n] << '\n';
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 11057] 오르막 수  (0) 2020.01.22
[백준 10844] 쉬운 계단 수  (0) 2020.01.22
[백준 9095] 1,2,3 더하기  (0) 2020.01.20
[백준 11727] 2×n 타일링 2  (0) 2020.01.20
[백준 11726] 2×n 타일링  (0) 2020.01.20
[백준 1463] 1로 만들기  (0) 2020.01.20
0 Comments
댓글쓰기 폼