프로그래머스 Lv.3) 2xn 타일링

2 x n 타일링

프로그래머스

풀이

코드 1

 

이 문제도 풀었었는데..?? 하는 생각이 들었다. 나중에 알고보니 백준에 타일링 시리즈가 많다는 것을 들었다. 

dfs의 로직을 dp로 옮기는 문제 중 가장 기본인 문제라고 생각한다.

이 문제는 피보나치 수열을 이용하는 문제로 무리없이 풀 수 있었다.

 

---

2020.06.03) 코드 2

얼마 전, 멀리뛰기 문제를 풀면서, 피보나치를 배열이 아닌 세 변수를 이용해 푼 기억이 났다.

그래서 이 문제에서도 배열이 아닌, 변수 세 개를 이용해 풀면서 완벽히 숙지했나 확인하려고 다시 풀었다.

개인적으로 코드의 길이는 비슷하지만, 효율이 조금 더 좋다는 점에서 마음에 드는 풀이법이다.

 

프로그래머스 Lv.3) 멀리 뛰기

 

 

코드 1

 

public class Tiling_12900 {
    private static int solution(int n) {
        int answer =0;
        if(n ==1 || n==2) {
            answer = n;
        } else {
            long[] dp = new long[n + 1];
            dp[1] =1;
            dp[2] =2;

            for(int i=3; i<=n; i++) {
                dp[i] = dp[i-1]%1000000007 + dp[i-2]%1000000007;
            }
            answer = (int)(dp[n]%1000000007);
        }
        return answer;
    }

    public static void main(String[] args) {
        int n =5;
        System.out.println(solution(n));
    }
}

 

 

코드 2

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        final int MOD = 1000000007;
        int left =1;
        int right =2;
        if(n ==1) {
            answer =left;
        } else if(n==2) {
            answer =right;
        } else {
            for(int i=2; i<n; i++) {    //3 ~> 한번 진행 
                answer =(left+right) % MOD;
                left = right;
                right = answer;
            }
        }
        return answer;
    }
}