2 x n 타일링
문제: https://programmers.co.kr/learn/courses/30/lessons/12900
1. 문제 설명
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.
타일을 가로로 배치 하는 경우
타일을 세로로 배치 하는 경우
예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
가로의 길이 n은 60,000이하의 자연수 입니다.
경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
2. 나의 코드
1) 재귀 함수를 이용하여 푸는 방법
- 사실 처음에는 트리 모양을 생각했다. n을 값으로 가지는 루트노드를 설정하고,
- 가지를 치면서 내려가는 데, 단 왼쪽 차일드 노드로 내려갈때는 -1을 하고 오른쪽 차일드 노드로 내려갈 때는 -2를 한다.
- 그렇게 내려가다 n이 0이 되면 방법 한가지를 찾은 것이므로 1을 리턴하고 n < 0이면 못찾은 것이므로 0을 리턴한다.
- 이것을 재귀함수로 만들면 다음과 같다.
class Solution {
public int solution(int n) {
int answer = 0;
answer = find(n);
return answer;
}
public int find(int n){
if(n == 0){
return 1;
}
else if(n < 0){
return 0;
}
else{
return (find(n-1) + find(n-2));
}
}
}
2) Dynamic Programming을 이용하여 푸는 법
- 하지만 주어진 값이 너무 커서 시간이 많이 걸리는 문제가 생겼다. 그래서 위의 코드를 DP로 풀었다.
- 재귀함수로 풀어놓고 보니 피보나치와 유사한 코드가 되었다. 그래서 그것을 참고하여 바꾸어보았다.
- 배열을 이용하여 풀기 때문에, n<0을 표현할 수가 없다. index는 음수가 될수없으므로..(자바에 한해서)
- 따라서, n = 1일때, 항상 1가지 방법밖에 없고 무조건 방법이 있으므로 1을 리턴한다.
- 결국 다음과 같은 DP를 이용한 코드를 짤 수 있다.
import java.util.*;
class Solution {
public int solution(int n) {
int answer = 0;
answer = find(n);
return answer;
}
public int find(int n){
int [] findArr = new int[n+1];
findArr[0] = 1;
findArr[1] = 1;
for(int i=2; i<=n ;i++){
findArr[i] = (findArr[i-1]+findArr[i-2])%1000000007;
}
return findArr[n];
}
}
