[ 백준 3019 ] 테트리스 (C++)

백준의 테트리스(3019) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 필드가 주어지고 테트리스 블록의 각 모양들을 놓았을 때, 빈칸이 생기기 않도록 놓을 수 있는 전체 경우의 수를 구하는 것이다.

[ 문제풀이 ]

1. 7개의 블록에 대해서 (7개의 블록은 문제 보고 올 것) 모든 회전하는 경우를 다 고려해 줘야 한다.

2. 본인은 입력으로 주어지는 필드의 상태와 도형의 상태를 이용해보았다.

   필드는 현재까지 쌓여진 높이가 주어진다. 이 높이를 이용해서 생각을 해보자.

   예를 들어서,

   이 모양에 대해서 생각해보자. 그리고 필드가 예를 들어서 2 1 0 0 0 0 2 인 상태라고 해보자.

   이 모양을 세로로 놓는다고 가정했을 때, 몇가지 경우가 있을까? 어느 열이든 다 놓을 수 있다. 어디에 놓든지 빈공간이 생기지

   않기 때문이다. 그렇다면 가로로 눕혔을 때를 생각해보자. 제일 처음 숫자인 2에는 못놓을 것이다. 왜냐하면 옆에 높이가

   1 0 0 0... 식이기 때문에 아마 빈공간이 생기게 될것이다. 즉 놓을 수 있는 곳은 0 0 0 0 이 한군데 뿐일 것이다.
   그렇다면 이번에는 도형의 상태를 생각해보자. 저 도형을 세로로 놓았을 때 왜 어디든지 놓을 수 있었을까?

   정답은 도형의 좌우의 높이차이가 없기 때문이다. 다른 도형들과 달리, 저 막대는 열을 하나만 차지한다. 다른 도형과

   비교해서 설명해 보겠다.

   이렇게 저 도형은 열을 하나만 차지하기 때문에 그런것이었다.

   즉, 도형이 차지하는 열의 길이와, 도형이 가지고 있는 높이차이를 이용한다면 쉽게 생각해낼 수 있다.

   쉽게 말해서, 아래 두 도형을 보면...

3번 같은 경우에는 (x,y)와 (x, y+1)의 높이가 같아야하고, (x, y+2)와는 높이차이가 1이 나야한다.

   즉 0 0 1 맵이 이런경우에 놓을 수 있는 것이다. 물론 90도를 회전한 경우도 생각해 봐야 한다. 3번을 머릿속으로 90도 회전시켜보

   자. 그렇다면 아마 결과는 왼쪽의 높이가 1이 더 높은 지형일 때만 놓을 수 있을 것이다.

   이 부분을 코드로만 구현하면 되기 때문에 코드를 본다면 더쉽게 이해할 것이다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int C, P, Answer;
int MAP[MAX];
 
void Input()
{
    cin >> C >> P;
    for (int i = 0; i < C; i++)
    {
        cin >> MAP[i];
    }
}
 
void Shape1()
{
    Answer = Answer + C;
    for (int i = 0; i < C - 3; i++)
    {
        if (MAP[i] == MAP[i + 1] && MAP[i + 1] == MAP[i + 2] && MAP[i + 2] == MAP[i + 3]) Answer++;
    }
}
 
void Shape2()
{
    for (int i = 0; i < C - 1; i++)
    {
        if (MAP[i] == MAP[i + 1]) Answer++;
    }
}
 
void Shape3()
{
    for (int i = 0; i < C - 2; i++)
    {
        if (MAP[i] == MAP[i + 1] && MAP[i + 1] == MAP[i + 2] - 1) Answer++;
    }
    for (int i = 0; i < C - 1; i++)
    {
        if (MAP[i] == MAP[i + 1] + 1) Answer++;
    }
}
 
void Shape4()
{
    for (int i = 0; i < C - 2; i++)
    {
        if (MAP[i] == MAP[i + 1] + 1 && MAP[i + 1] == MAP[i + 2]) Answer++;
    }
    for (int i = 0; i < C - 1; i++)
    {
        if (MAP[i] == MAP[i + 1] - 1) Answer++;
    }
}
 
void Shape5()
{
    for (int i = 0; i < C - 2; i++)
    {
        if (MAP[i] == MAP[i + 1] && MAP[i + 1] == MAP[i + 2]) Answer++;
        if (MAP[i] == MAP[i + 1] + 1 && MAP[i + 1] == MAP[i + 2] - 1) Answer++;
    }
    for (int i = 0; i < C - 1; i++)
    {
        if (MAP[i] == MAP[i + 1] - 1) Answer++;
        if (MAP[i] == MAP[i + 1] + 1) Answer++;
    }
}
 
void Shape6()
{
    for (int i = 0; i < C - 2; i++)
    {
        if (MAP[i] == MAP[i + 1] && MAP[i + 1] == MAP[i + 2]) Answer++;
        if (MAP[i] == MAP[i + 1] - 1 && MAP[i + 1] == MAP[i + 2]) Answer++;
    }
    for (int i = 0; i < C - 1; i++)
    {
        if (MAP[i] == MAP[i + 1]) Answer++;
        if (MAP[i] == MAP[i + 1] + 2) Answer++;
    }
}
 
void Shape7()
{
    for (int i = 0; i < C - 2; i++)
    {
        if (MAP[i] == MAP[i + 1] && MAP[i + 1] == MAP[i + 2]) Answer++;
        if (MAP[i] == MAP[i + 1] && MAP[i + 1] == MAP[i + 2] + 1) Answer++;
    }
    for (int i = 0; i < C - 1; i++)
    {
        if (MAP[i] == MAP[i + 1] - 2) Answer++;
        if (MAP[i] == MAP[i + 1]) Answer++;
    }
}
 
void Solution()
{
    if (P == 1) Shape1();
    else if (P == 2) Shape2();
    else if (P == 3) Shape3();
    else if (P == 4) Shape4();
    else if (P == 5) Shape5();
    else if (P == 6) Shape6();
    else if (P == 7) Shape7();
    
    cout << Answer << 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;
}