알고리즘/koreatech
1055: 판 채우기
cjw.git
2020. 12. 11. 10:33
Link : judge.koreatech.ac.kr/problem.php?id=1055
1. 문제
- 3 * N 의 판이 있습니다. 이 판을 1 * 1 짜리 블럭과 2 * 2 블럭들을 이용해서 빈틈없이 채우려고 합니다.
길이 N이 주어 졌을 때, 몇 가지 방법으로 채울 수 있는지 구해 주세요.
2. 문제의 조건
- 1 <= T <= 10
- 1 <= N <= 100
- 1,000,000,007로 나눈 나머지를 출력
더보기
3. 문제 접근
- 시간 복잡도
1초 이내의 시간에 총 1000개를 푸는 문제라서 O(N^2.66)시간 이내에 풀면 됩니다!
- 아이디어
전형적인 dp문제 입니다.
3*N의 판에선 총 2개만 고려하시면 됩니다.
n이 길이가 1인 경우
3 * 1을 채울수 있는 경우의수는 1*1을 3개 이용한 1가지입니다.
또한, n이 길이가 2인 경우
해당 2가지의 경우로 나뉘어집니다.
이를 점화식으로 세우면 d(n-1) + 2*(n-2)가 됩니다.
※ n-3부턴 n-1와 n-2의 조합으로 만들 수 있으니 점화식에 계산(추가)하지 않습니다.
dp와 메모이제이션을 이용한 점화식이므로 시간 복잡도는 O(N)이 되어 충분히 풀 수 있습니다.
4. 풀이 방법
- dp를 수행 할 배열을 n + 1개만큼 만들어줍니다.
- 3 * 1(n)일 땐 경우의 수가 1이고, 3 * 2(n)일땐 경우의 수가 총 3가지이므로
dp[1] = 1이되고 dp[2] = 3이 됩니다. - 1과 2를 구했으니 3부터 n+1번째 까지 점화식을 수행합니다.
- dp[n]번쨰를 구해줍니다.
5. 소스코드
cjw.git@gmail.com