11726
-
백준(BOJ) 11726번 2xn 타일링알고리즘 풀이/백준(Boj) 2019. 7. 6. 02:45
문제 : https://www.acmicpc.net/problem/11726 입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 나의풀이 : 세로줄 왼쪽부터 채워나갈수 있는 경우의 수를 생각해보자. 세로로 한개, 가로로 두개 두 경우 이외에는 없기 때문에재귀적으로 구현해주고 n이 1000까지 있기에 완전 탐색으로는 시간 내에 불가능하니 메모이제이션을 적용해서 중복되는 탐색을 방지하자. 코드 ( C ++ ) #include #include using namespace std;int N;const int MAX = 1000;int cache[MAX+1]; // n이 1000일 경우 cache[1000]이 ..