[ 백준 13301 ] 타일 장식물 (C++)

백준의 타일 장식물(13301) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저, 본격적인 문제를 풀기전에 수식을 하나 정해놓고, 이 수식을 바탕으로 문제를 해결해 나가보자.

F[A][B] = C 라는 수식을 사용할 것이다.

먼저, 'B'부분의 크기는 '2'이다. 즉, 실질적으로 사용할 수 있는 인덱스는 0번과 1번 인덱스 이렇게 2개만 존재하게 된다.

그럼 결과적으로 F[A][0] = C , F[A][1] = C 라는 이런식의 수식을 사용하게 될 것인데, 이 수식의 의미는 다음과 같다.

F[A][0] = C : A번째 타일장식물의 가로길이는 C입니다.

F[A][1] = C : A번째 타일장식물의 세로길이는 C입니다.

그런데, 문제에서 주어진 그림과는 조금은 다른 형태로 문제에 접근해보고자 한다.

이 부분은 밑에서 진행하면서 같이 알아보자.

그럼 작은 장식물부터 하나하나 그림을 그려가면서 접근해보자.

#1. 1번 장식물

.

1번 장식물은 가로와 길이 모두 길이가 '1'인 작은 정사각형이다.

이를 수식을 이용해서 저장을 해보면

F[1][0] = 1

F[1][1] = 1 로 저장할 수 있다.

#2. 2번 장식물

.

2번 장식물은, 1번 장식물 밑에 또 다른 1번장식물이 붙은 형태로, 세로로 길쭉한 형태로 그려져 있다.

문제에 주어진 그림으로는 다음과 같이 표현되어 있다.

.

위와 같은 형태로 표현되어있는데, 위와 같은 형태로 표현하는 것이 아니라, 그 위에 길쭉한 하나의 사각형으로 생각하겠다.

결과적으로 우리는 N번째 사각형의 둘레의 길이를 구하면 되는 것이다.

그럼 이 2번장식물에 대한 가로, 세로 길이를 수식으로 저장해보자.

F[2][0] = 1

F[2][1] = 2 가 된다.

가로가 1, 세로가 2인 세로로 길쭉한 직사각형이므로, 위와 같은 수식으로 저장할 수 있다.

#3. 3번 장식물

.

문제에서는 위와 같이 표현되어 있는 사각형이다. 이를 하나로 그려보면 다음과 같이 표현할 수 있다.

.

이 사각형의 세로길이는 2, 가로길이는 3이 된다.

즉, F[3][0] = 3

F[3][1] = 2 가 된다.

#4. 4번 장식물

.

문제에서 위와 같이 표현되어 있는 사각형이다. 이를 하나로 그려보면 다음과 같이 그려볼 수 있다.

.

위와 같이 하나의 사각형으로 표현할 수 있는데, 계산을 해보면 이 사각형의 세로길이는 5, 가로길이는 3이 된다.

F[4][0] = 3

F[4][1] = 5

# 규칙

그럼 지금까지 1 ~ 4번 장식물에 대한 가로 ,세로 길이를 모두 구해봤는데, 이제는 하나의 일반화된 식을 찾아보자.

각 장식물들의 변의 길이를 [ 가로 , 세로 ] 로 적어본다면..

1번 장식물 = [ 1 , 1 ]

2번 장식물 = [ 1 , 2 ]

3번 장식물 = [ 3 , 2 ]

4번 장식물 = [ 3 , 5 ]

위와 같이 적어볼 수 있다.

본인은 여기서 하나의 규칙을 발견했다.

바로, "이전의 가로 + 세로의 길이가, 그 다음 장식물의 어떤 한 변의 길이가 된다." 라는 것이다.

1번 장식물의 가로 + 세로 길이는 1 + 1 로 '2'가 된다.

이 '2'는 2번 장식물의 세로 길이가 된다.

2번 장식물의 가로 + 세로 길이는 1 + 2 로 '3'이 된다.

이 '3'은 3번 장식물의 가로 길이가 된다.

3번 장식물의 가로 + 세로 길이는 3 + 2 로 '5'가 된다.

이 '5'는 4번 장식물의 세로 길이가 된다.

이런 규칙이 하나 있다.

그런데, 어떤 경우에는, 그 길이가 그 다음 장식물의 세로 길이가 되고, 어떤 경우에는 그 다음 장식물의 가로 길이가 된다.

어떤 차이가 있을까 ??

바로, "짝수번 장식물"과 "홀수번 장식물" 이라는 차이가 있다.

짝수번 장식물들의 경우에는, "이전 장식물의 가로 길이를 가로로, 이전 장식물의 가로 + 세로 길이를 세로로" 가져오게 되고,

홀수번 장식물들의 경우에는, "이전 장식물의 세로 길이를 세로로, 이전 장식물의 가로 + 세로 길이를 가로로" 가져오게 된다.

2번 장식물을 예로 들어보자.

위의 말대로라면, 2번 장식물의 가로길이는, 1번장식물의 가로길이가 될 것이고, 2번 장식물의 세로길이는, 1번 장식물의 가로 + 세로 길이가 될 것이다. 한번 확인해보자.

2번 장식물의 가로길이는 '1'이고, 이는 '1번 장식물의 가로길이(1)' 와 동일하다.

2번 장식물의 세로길이는 '2'이고, 이는 '1번 장식물의 가로(1) + 세로(1)' 와 동일하다.

3번 장식물을 생각해보자.

위의 말대로라면, 3번 장식물의 가로길이는, 2번 장식물의 가로 + 세로 길이가 될 것이고, 3번 장식무르이 세로길이는, 2번 장식물의 세로 길이가 될 것이다. 한번 확인해보자.

3번 장식물의 가로길이는 '3'이고, 이는 '2번 장식물의 가로(1) + 세로(2)' 와 동일하다.

3번 장식물의 세로길이는 '2'이고, 이는 '2번 장식물의 세로(2)' 와 동일하다.

즉, 홀수번 장식물이나 짝수번 장식물이냐에 따라서 서로 다르게 규칙이 적용된다.

이를 우리가 정해놨던 수식으로 만들어보자.

# 최종 점화식

"N번째 장식물의 가로와 세로길이" 를 구해보자.

먼저, N이 짝수인 경우이다. 짝수번 장식물들의 경우에는 가로의 길이는 이전 장식물의 가로 길이를 그대로 가져오게 된다.

즉, F[N][0] = F[N - 1][0] 가 된다.

세로의 길이는, 이전 장식물의 가로 + 세로 길이를 가져오게 된다.

F[N][1] = F[N - 1][0] + F[N - 1][1] 이 된다.

두 번째로 홀수인 경우이다. 홀수인 장식물들의 경우에는 세로의 길이는 이전 장식물의 세로 길이를 그대로 가져오게 된다.

F[N][1] = F[N - 1][1]

가로의 길이는, 이전 장식물의 가로 + 세로 길이를 가져오게 된다.

F[N][0] = F[N - 1][0] + F[N - 1][1] 이 된다.

정리해보면....

1) N이 짝수인 경우

F[N][0] = F[N - 1][0]

F[N][1] = F[N - 1][0] + F[N - 1][1]

2) N이 홀수인 경우

F[N][1] = F[N - 1][1]

F[N][0] = F[N - 1][0] + F[N - 1][1] 이 된다.

이를 점화식으로 문제를 해결할 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 85
using namespace std;
 
int N;
long long Line[MAX][2];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    // Line[1][0] = 1번째 장식물의 가로길이
    // Line[1][1] = 1번째 장식물의 세로길이
    Line[1][0] = 1;
    Line[1][1] = 1;
    for (int i = 2; i <= N; i++)
    {
        if (i % 2 == 0)
        {
            Line[i][1] = Line[i - 1][0] + Line[i - 1][1];
            Line[i][0] = Line[i - 1][0];
        }
        else
        {
            Line[i][0] = Line[i - 1][0] + Line[i - 1][1];
            Line[i][1] = Line[i - 1][1];
        }
    }
    cout << Line[N][0] * 2 + Line[N][1] * 2 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}