Menu

Subscribe

[JAVA/프로그래머스] 동적계획법(Dynamic Programming)_타일 장식물

HEESOO on Programmers

👀 문제

https://programmers.co.kr/learn/courses/30/lessons/43104

👊 도전

1. 설계

  1. 타일의 규칙은 피보나치 수열이므로 N까지의 피보나치 값을 계산한다.
  2. N개의 타일로 구성한 직사각형의 둘레는 4x현재 타일+2x이전 타일이다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public long solution(int N) {
        long answer = 0;
        long[] fib=new long[N];
        fib[0]=1;
        fib[1]=1;
        for(int i=2;i<N;i++){//피보나치 계산
            fib[i]=fib[i-1]+fib[i-2];
        }
        answer=4*fib[N-1]+2*fib[N-2];
        return answer;
    }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 타일의 길이는 피보나치 수열 규칙을 가진다.
    • 타일은 1 1 2 3 5 8 …와 같이 진행되므로 피보나치수열이다.
    • N까지의 피보나치 수열을 계산해서 저장한다. 피보나치수열은 보통 재귀함수를 배울때 대표적인 예시인데, 나는 배열을 통해 계산했다.
  2. 직사각형 둘레 길이는 4x현재+2x이전타일이다.
    예시
    • 위 그림을 통해 4x현재길이+2x이전길이를 만족함을 알 수 있다.
    • 처음에는 2*(현재길이+(이전길이+이이전길이))를 생각했는데, 이 공식은 총 세개의 타일 길이 값을 사용해야해서 효율성이 떨어진다.

👏 해결 완료!

문제를 읽었을 때는 막막했는데, 막상 풀이법은 간단했다. 아직은 문제를 보면 어떻게 해결해야할지 감이 안온다.

참고