본문 바로가기
Baekjoon/[Code.plus] 알고리즘 기초 1/2

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

by 해적거북 2021. 7. 30.
728x90

● [문제번호 11727] 2×n 타일링 2

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

 

11727번: 2×n 타일링 2

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

www.acmicpc.net

 

● 알아야 할 것

: [BOJ/백준] 11726 2×n 타일링

: 다이나믹 프로그래밍

: vector 자료구조와 메소드

 

● 풀이 과정

: (이전 문제) [BOJ/백준] 11726 2×n 타일링

를 풀어봤다면 1줄의 코드만 수정하여 해결할 수 있다.

 

: 2×2 타일이 추가되었는데

이것은 1×2 타일 2개와 똑같다.

 

: DP의 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ 각 index의 값은 '2×index의 타일로 채우는 방법의 수'를 나타낸다.

 

2. 점화식 찾기

→ dp[index] = dp[index - 1] + dp[index - 2]

 

2×1 타일 1개 추가하면 되는 경우 = dp[index - 1]

1×2 타일 2개 추가하면 되는 경우 = dp[index - 2]

2×2 타일 1개 추가하면 되는 경우 = dp[index - 2]

결국 (가로가 index인 타일을 채우는 방법의 수)는

(index - 1 인 타일을 채우는 방법의 수) + (index - 2 인 타일을 채우는 방법의 수) + (index - 2 인 타일을 채우는 방법의 수) 이다.

 

3. 초기값 정하기

dp[1] = 1

→ 2×1 타일 1개

 

dp[2] = 3

→ 2×1 타일 2개 또는 1×2 타일 2개 또는 2×2 타일 1개 

 

● 주의 할 것

: 매 index에서 타일을 채우는 방법의 수를 구할 때 마다 나머지 연산을 해야한다.

vector의 자료형을 long long으로 바꿔도 결과값에서만 나머지 연산을 하면 오답이 나온다.

 

● 참고 할 것

: (이전 문제) [BOJ/백준] 11726 2×n 타일링

https://pirateturtle.tistory.com/200

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// DP의 테이블
vector<int> dp;
int N;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    // 입력
    cin >> N;
    
    // index를 통해 확인하므로 N + 1개 할당 (0 index 사용은 선택적)
    dp.assign(N + 1, 0);
    
    // 초기값 설정
    dp[1] = 1;
    dp[2] = 3;
    
    // 다이나믹 프로그래밍 (Bottom - Up)
    for(int i = 3; i <= N; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 2]) % 10007;
    }
    
    // 구하고자하는 타일을 채우는 방법의 수
    cout << dp[N];

    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [400 - 다이나믹 프로그래밍 1] 문제집

번호 문제 번호 문제 이름 풀이 링크
1 1463 1로 만들기 https://pirateturtle.tistory.com/199
2 11726 2×n 타일링 https://pirateturtle.tistory.com/200
3 11727 2×n 타일링 2 https://pirateturtle.tistory.com/201
4 9095 1, 2, 3 더하기 https://pirateturtle.tistory.com/202
5 11052 카드 구매하기 https://pirateturtle.tistory.com/203
6 16194 카드 구매하기 2 https://pirateturtle.tistory.com/204
7 15990 1, 2, 3 더하기 5 https://pirateturtle.tistory.com/205
8 10844 쉬운 계단 수 https://pirateturtle.tistory.com/206
9 2193 이친수 https://pirateturtle.tistory.com/207
10 11053 가장 긴 증가하는 부분 수열 https://pirateturtle.tistory.com/208
11 14002 가장 긴 증가하는 부분 수열 4 https://pirateturtle.tistory.com/209
12 1912 연속합 https://pirateturtle.tistory.com/210
13 1699 제곱수의 합 https://pirateturtle.tistory.com/211
14 2225 합분해 https://pirateturtle.tistory.com/212

 

728x90

댓글