[프로그래머스/JAVA] 2 x n 타일링

문제

 

문제 설명
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

- 타일을 가로로 배치 하는 경우
- 타일을 세로로 배치 하는 경우

 

(중략)

 

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

 

풀이

내 답안 (틀린 답안)

class Solution {
    public int solution(int n) {
       
        int answer = fibonacci(n);
        return (answer%1000000007);
    }
    
    int fibonacci(int n) {
        if(n==1) { 
            return 1;
        } else if(n==2) { 
            return 2; 
        } else {
            return ( fibonacci(n-2) + fibonacci(n-1) );
        }
    }
}

사실 피보나치 수열인 것도 구글링해서 알았다.

이런 문제에서는 규칙성을 찾는게 중요한데, 지레 겁 먹고 차근차근히 접근해보지 않은게 실수였다.

피보나치 수열을 구현하고보니 타임 아웃이 됐다. 아무래도 계속 재귀가 되다보니 런타임이 길어졌나보다.

 

다른 사람의 답안

(참고: https://velog.io/@ajufresh/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-2-X-n-%ED%83%80%EC%9D%BC%EB%A7%81-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-Java )

public class Solution {
  public int solution(int n) {
    
    int answer = 0;

    int a = 1;
    int b = 1;

    for (int i = 1; i < n; i++) {
      answer = (a + b)  % 1000000007;
      
      a = b;
      b = answer;
    }
    
    return answer;
  }
}

여러 방법을 봤는데, 가장 간단하고 메모리 차치도 안하는 방법!

문제 과정에서 % 1000000007 해주는데, 이렇게 안하고 마지막에 % 1000000007을 해주면 overflow가 난다.

난 아직 멀었다 .. .. ..