[200424] 동적계획법(Dynamic Programming) - 타일장식물(level3)

1. 문제이해

- 정사각형 타일을 차례로 붙여나가면서 만들어진 큰 직사각형 둘레 구하기

  --> 결국은 "피보나치 수열"

 

2. 전략

① 상향식

- sumList : n개일때 가로+세로의 값 저장

- sumList[i] = sumList[i-1] + sumList[i-2]

② 하향식(시간 초과)

- sumCalculate(long N) : 재귀함수 이용

- sumCalculate(N-2) + sumCalculate(N-1)

 

3. 참고사항

- 효율성테스트 : 값이 커지면 int를 쓸 경우 범위를 벗어나 다른 결과가 나온다!!

                        --> long타입을 써야됨!!

 

4. 코드

class Solution {
    public long solution(int N) {
        long answer = 0;
        long[] sumList = new long[N+1];
        long start = 1;
        sumList[0] = 1;
        for(int i = 1; i <= N; i++){ //상향식
            if(i == 1){
                sumList[1] = sumList[0] + start;
            }
            else{
                sumList[i] = sumList[i-1] + sumList[i-2];
            }
        }
        answer = sumList[N] * 2;
        //answer = sumCalculate(N) * 2;
        return answer;
    }
    
    public int sumCalculate(long N){ //하향식 - 시간초과
        if(N == 1)  return 2;
        else if(N == 2) return 3;
        else{
            return (sumCalculate(N-2) + sumCalculate(N-1));
        }
    }
}