● [문제번호 11727] 2×n 타일링 2
https://www.acmicpc.net/problem/11727
● 알아야 할 것
: [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 |
'Baekjoon > [Code.plus] 알고리즘 기초 1/2' 카테고리의 다른 글
[BOJ/백준] 16194 카드 구매하기 2 (0) | 2021.07.30 |
---|---|
[BOJ/백준] 11052 카드 구매하기 (0) | 2021.07.30 |
[BOJ/백준] 9095 1, 2, 3 더하기 (0) | 2021.07.30 |
[BOJ/백준] 11726 2×n 타일링 (0) | 2021.07.30 |
[BOJ/백준] 1463 1로 만들기 (0) | 2021.07.30 |
[BOJ/백준] 11653 소인수분해 (0) | 2021.07.29 |
[BOJ/백준] 11576 Base Conversion (0) | 2021.07.29 |
댓글