Coding Test/프로그래머스
[200424] 동적계획법(Dynamic Programming) - 타일장식물(level3)
csmoon1010
2020. 4. 24. 12:51
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));
}
}
}