백준 - 타일 장식물 (C++)

Pixabay로부터 입수된 Gerd Altmann님의 이미지 입니다.

 

---

 

https://www.acmicpc.net/problem/13301

13301번: 타일 장식물

 

 이번 문제는 N이 주어질 때, 주어진 조건에 따라 N개의 타일로 구성된 직사각형의 둘레를 구하는 문제이다. 처음에는 규칙을 알아내려 했지만, 잡힐듯 말듯 한 것이 너무 아리송했다. 하지만 자세히 보니 규칙이 있었다.

 

 문제의 그림을 기준으로, 우선, N이 1일 경우는 정사각형이라 가로, 세로 길이가 각각 1이다. 그리고 N이 2일 때는 가로, 세로가 각각 1, 2이다. N이 3일 때는 가로가 3, 세로가 2이다. N이 4일 때에는 가로, 세로가 각각 3, 5이다. 하지만 직사각형이 가로가 길든 세로가 길든 답은 변하지 않으니, 편의상 가로가 더 길다고 하자. 이를 기준으로 다시 정리하자면 다음과 같다.

• N: 1 -> 1, 1
• N: 2 -> 2, 1
• N: 3 -> 3. 2
• N: 4 -> 5, 3
• N: 5 -> 8, 5

여기서 타일의 개수가 N일 때의 직사각형의 가로는 N - 1일 때의 가로 + 세로와 같으며 세로는 N - 1일 때의 가로와 같은 것을 알 수 있다. 이를 코드에 적용하면 다음과 같다.

 

#include <iostream>

using namespace std;

int N;
pair<long long, long long> dp[1000000]; // first: 가로, second: 세로

pair<long long, long long> Check(int num)
{
    if (dp[num].first != -1)
        return dp[num];

    pair<long long, long long> befRec = Check(num - 1);
	
    // 가로: 이전 직사각형의 가로 + 이전 직사각형의 세로
    // 세로: 이전 직사각형의 가로
    return dp[num] = { befRec.first + befRec.second, befRec.first };
}

int main()
{
    ios_base::sync_with_stdio(0);
	std::cout.tie(NULL);    
	std::cin.tie(NULL);

    for (int i = 1; i <= 1000000; ++i)  
        dp[i] = { -1, -1 };

    dp[1] = { 1, 1 };
    dp[2] = { 2, 1 };

    cin >> N;

    pair<long long, long long> rectangle = Check(N);
	
    // 직사각형의 둘레는 (가로 + 세로) * 2
    long long answer =  (rectangle.first + rectangle.second) * 2;

    cout << answer << endl;

    return 0;
}