Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- HashSet
- Dynamic Programming
- Java
- 후위 표기법
- 쿼드압축 후 개수세기
- fragment identifier
- 순열
- 영문자 확인
- dfs
- 완전 탐색
- 완전탐색
- 조합
- HashMap
- 문자열
- 2017 카카오 코드
- 메뉴리뉴얼
- 점프와 순간이동
- 반복문
- 에라토스테네스의 체
- 규칙찾기
- 프로그래머스
- 보이어무어
- 최소공배수
- 어려웠던 문제
- 동적계획법
- 알고리즘
- pandas
- Stack
- python
- 튜플
Archives
- Today
- Total
csmoon1010의 SW 블로그
[200424] 동적계획법(Dynamic Programming) - 타일장식물(level3) 본문
Coding Test/프로그래머스
[200424] 동적계획법(Dynamic Programming) - 타일장식물(level3)
csmoon1010 2020. 4. 24. 12:511. 문제이해
- 정사각형 타일을 차례로 붙여나가면서 만들어진 큰 직사각형 둘레 구하기
--> 결국은 "피보나치 수열"
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));
}
}
}
'Coding Test > 프로그래머스' 카테고리의 다른 글
[200425] 그래프 - 가장 먼 노드(level3) (0) | 2020.04.25 |
---|---|
[200424] 이분탐색(Binary Search) - 예산(level3) (0) | 2020.04.24 |
[200424] 동적계획법(Dynamic Programming) - N으로 표현(level3) (0) | 2020.04.24 |
[200421] 탐욕법(Greedy) - 섬 연결하기(level3) (0) | 2020.04.24 |
[200421] 탐욕법(Greedy) - 구명보트(level2) (0) | 2020.04.24 |
Comments