컴공댕이 공부일지
[ C++/cpp ] 백준 (11726 2×n 타일링) ⭐다이나믹프로그래밍 본문
백준 11726번 2×n 타일링
(실버 3)
https://www.acmicpc.net/problem/11726
(정답 코드)
#include <iostream>
#include <vector>
#define MOD 10007 // 상수값은 깔끔하게 define 해두기
using namespace std;
// 피보나치 bottomup
int solution(int n) {
vector<int> v (n+1, -1); // n+1칸 벡터 초기화
v[0]=1;
v[1]=1;
for(int i=2; i<=n; i++) {
v[i] = v[i-1] + v[i-2];
v[i] %= MOD;
}
return v[n] % MOD;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
cout << solution(n);
return 0;
}
📖 풀이
- N=1일 때, 2x1 크기의 직사각형을 채우는 방법은 1가지.
- |ㅁ|
- N=2일 때, 2x2 크기의 직사각형을 채우는 방법은 2가지.
- |ㅁㅁ| (세로로 2개)
- |ㅡ| |ㅡ| (가로로 2개)
- N=3일 때, N=2에 1x2 타일 하나를 추가하는 방법과 N=1에 2x1 타일 두 개를 추가하는 방법이 결합되어 총 3가지
- |ㅁㅁ| |ㅁ|
- |ㅁ| |ㅡ| |ㅡ|
- |ㅡ| |ㅡ| |ㅁ|
- N=4일 때는 N=3에 1x2 타일 하나를 추가하는 방법과 N=2에 2x1 타일 두 개를 추가하는 방법이 결합되어 총 5가지
- |ㅁㅁ| |ㅁㅁ|
- |ㅁㅁ| |ㅡ| |ㅡ|
- |ㅁ| |ㅡ| |ㅡ| |ㅁ|
- |ㅡ| |ㅡ| |ㅁㅁ|
- |ㅡ| |ㅡ| |ㅡ| |ㅡ|
- N=5일 때는 N=4에 1x2 타일 하나를 추가하는 방법과 N=3에 2x1 타일 두 개를 추가하는 방법이 결합되어 총 8가지
위 과정처럼, n = 1부터 한 5까지 벽돌 하나하나 그려보다보면 익숙한 규칙이 보이고 그건 바로 피보나치다. 전형적인 DP 문제 ! 사실상 피보나치 수열 구하는 문제다. 나는 DP 바텀업 방식으로 풀어보았다.
참고로 탑다운은 재귀로 구현하여 함수를 여러번 호출해야해서, for 반복문 한 번 도는 바텀업 방식이 더 빠르다~
이번에 DP 다시 공부하면서 안 사실,, 바텀업 방식이랑 탑다운 방식이 시간 복잡도는 같아도, 바텀업 방식이 실제로 더 빠르다고 한다. 바텀업 방식이 반복문을 통해 한 번만 계산하는 반면, 탑다운 방식은 재귀 호출로 여러 번 계산하기 때문.
# 10007 나누기
문제 요구사항 따라, 연산 중간중간 오버플로우 안나게 10007만 나눠주면 되어서 반복문마다 나눠줬다. 왜중간중간 나눠주어야 하냐면.. n 범위가 1000까지인데 피보나치 수열 1000번째 값은 .. 어마무시하다.
참고로 연산 중간중간 나눠주어도 최종 값엔 영향이 없다. 두 수를 더한 후 나머지를 취하든, 나머지를 먼저 취한 두 수를 더하든 결과가 같다는 성질이 있기 때문.
ex. (7%3) + (9%3) = (7+9) % 3
이게 되나 맞나 싶을 땐 그냥 아무 숫자나 예시로 해보면 증명이 쉽다.
# 런타임 에러 - DoubleFree (double free or corruption)
첨에 벡터 크기 n으로 해버려서, v[n] 접근하면서 런타임 에러가 떴다. 바보
너무도 기초적인 사실이지만.. n칸 인덱스까지 사용하려면 n+1칸을 초기화해야한다..ㅎ
'문제 풀이 > 코딩 문제 풀이 모음' 카테고리의 다른 글
[ C++/cpp ] 백준 (5430 AC) ⭐구현, 덱 (5) | 2024.10.08 |
---|---|
[ C++/cpp ] 백준 (1654 랜선 자르기) ⭐이분 탐색 💦 (0) | 2024.07.20 |
[ C++/cpp ] 백준 (11561 좌표 정렬하기2) ⭐pair vector 정렬, 비교함수 (0) | 2024.07.18 |
[ C++/cpp ] 백준 (2108 통계학) ⭐최빈값 구하기, 최장 길이 부분 수열 (0) | 2024.07.11 |
[ C++/cpp ] 백준 (1018 체스판 다시 칠하기) ⭐브루트포스 알고리즘 (1) | 2024.03.29 |