프로그래머스 - 타일 장식물

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

 

문제 설명

정사각형 타일을 붙여 만든 형태의 타일 장식물이 있다. 이 장식물은 한 변이 1인 정사각형 타일부터 시작해서, 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태다.
(링크의 문제에서 그림을 확인해보자)

한 변의 가장 긴 쪽의 길이의 정사각형을 붙여나가는 방식으로 붙여나가면, 정사각형의 한 변의 길이는 차례대로 다음과 같이 된다.

[1,1,2,3,5,8,...]

N개의 타일로 만든 직사각형 장식물의 둘레를 리턴하자.

 

제한 사항

• 1 <= N <= 80

 

1. 피보니치(DP) - O(N)

사실 문제를 읽다보면 “이 문제는 피보나치 수로 풀어야 하는구나!” 라는 생각이 들 것이다. 대놓고 정사각형의 길이가 피보나치 수로 증가한다는 것을 보여주고 있기 때문이다. 피보나치라는 것을 알고 풀면, 레벨 3이라는 타이틀이 무색해질 정도로 쉬워진다.

피보나치인걸 알았다면, i번째 정사각형 타일의 길이 d[i]는 다음과 같을 것이라는 것도 쉽게 파악할 수 있다.

d[i] = d[i-1] + d[i-2] (d[1] = d[2] = 1)

하지만 우리가 구해야 하는 것은 장식물의 둘레다. i번째 정사각형의 타일의 길이를 토대로 타일의 둘레를 구해야 한다.

i개의 정사각형을 사용했을 때, 짧은 쪽의 길이는 어떻게 될까? 그림을 보면 알겠지만 d[i]가 된다.
그러면 긴 쪽의 길이는 어떻게 될까? 역시 그림을 보면 알겠지만 d[i] + d[i-1]이 된다.

사각형의 둘레를 구하기 위해선 2 x (긴 쪽의 길이 + 짧은 쪽의 길이) 의 값을 구하면 된다. 그러면 i개의 정사각형을 사용했을 때, 긴 쪽의 길이 + 짧은 쪽의 길이를 구한 값인 D[i]는 다음과 같이 표현할 수 있을 것이다.

D[i] = D[i-1] + D[i-2] (D[1] = 2, D[2] = 3)

그리고 답은 둘레를 구하는 것이니, 2 x D[i]를 리턴하면 될 것이다.

 

배열을 N+1만큼 잡아두고, 피보나치 수를 구하면 된다.

 

solution_array.cpp

#include <vector>

using namespace std;

long long solution(int N) {
    vector<long long> D(N+1, 0);
    D[0] = 1;   D[1] = 2;
    
    for (int i=2;i<=N;++i)
        D[i] = D[i-1] + D[i-2];
    
    return 2*D[N];   
}

 

D[0]은 원래라면 존재하지 않는 값이지만, D[2]를 구하기 위해 넣어둔 값이라고 생각하자.

하지만 우리가 궁금한 값은 D[i-1]과 D[i-2] 뿐이다. D[i-3]부터는 필요없는 값이다. 그리고 D[i-2]도 D[i]를 구하고 난 뒤에는 관심없는 값이 되어 버린다.

따라서, 다음과 같이 2개의 변수만을 사용해서 구할 수도 있다.

 

solution_two_variables.cpp

#include <vector>

using namespace std;

long long solution(int N) {
    long long l = 1, r = 2;
    while (--N)
        (l < r) ? (l += r) : (r += l);    
    return 2 * max(l,r);
}

 

3레벨 치곤 굉장히 쉬운문제이긴 하다.
피보나치 수도 점화식의 일종이란 걸 다시 한 번 되새기고 넘어가자.