반응형
문제 보기
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
문제
입력
출력
| 시간 제한 | 메모리 제한 |
| 2 초 | 512 MB |
풀이방법
문제를 이해하는 것이 조금 어려운데
2차원 배열 위에 테트리스 조각을 놓아,
테트리스 조각이 놓인 곳의 숫자들의 합기 최대가 되도록 만드는 문제이다.
예제 1을 확인해 보자
예제 입력 1
5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1예제 출력 1
19
어디에 테트리스 조각을 놓았길래 19가 나왔을까?
4 + 4 + 5 + 6 = 19
해당 위치에 ㄱ자가 반전 된 모양의 조각을 넣었더니 출력값을 확인할 수 있었다.
그럼 문제를 이해하였으니 본격적으로 풀이 방법에 대해 알아보자.
나는 대학생 시절 C# 소켓통신을 사용한 멀티 테트리스를 만들어 본 경험이 있어서
쉽게 풀이 방법을 유추할 수 있었다.
공개하기 부끄러우나 혹시 관심이 있다면 아래 링크에서 확인할 수 있다.
https://github.com/MetroDefro/TetrisProject
GitHub - MetroDefro/TetrisProject
Contribute to MetroDefro/TetrisProject development by creating an account on GitHub.
github.com
그렇게 유추한 것이 무엇이냐면?
일단 테트리스 조각들을 어떻게 표현할 것인가이다.
구현 방법은 아래와 같다.
우선 byte 3차원 배열을 사용하였고
19개의 테트리스 조각을 4x4 배열(테트리스 조각이 잡아먹을 수 있는 최대 칸 수 고려) 안에 그려 넣었다.
byte[,,] tetris = {
{ {1, 1, 0, 0 },
{1, 1, 0, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 1, 1 },
{0, 0, 0, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 0, 0, 0 },
{1, 0, 0, 0 },
{1, 0, 0, 0 },
{1, 0, 0, 0 } } ,
{ {1, 0, 0, 0 },
{1, 0, 0, 0 },
{1, 1, 0, 0 },
{0, 0, 0, 0 } } ,
{ {0, 0, 1, 0 },
{1, 1, 1, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 0, 0 },
{0, 1, 0, 0 },
{0, 1, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 1, 0 },
{1, 0, 0, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {0, 1, 0, 0 },
{0, 1, 0, 0 },
{1, 1, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 1, 0 },
{0, 0, 1, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 0, 0 },
{1, 0, 0, 0 },
{1, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 0, 0, 0 },
{1, 1, 1, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 0, 0, 0 },
{1, 1, 0, 0 },
{0, 1, 0, 0 },
{0, 0, 0, 0 } } ,
{ {0, 1, 1, 0 },
{1, 1, 0, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {0, 1, 0, 0 },
{1, 1, 0, 0 },
{1, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 0, 0 },
{0, 1, 1, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {0, 1, 0, 0 },
{1, 1, 1, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {0, 1, 0, 0 },
{1, 1, 0, 0 },
{0, 1, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 1, 0 },
{0, 1, 0, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 0, 0, 0 },
{1, 1, 0, 0 },
{1, 0, 0, 0 },
{0, 0, 0, 0 } } ,
};
bool 배열로도 구현 가능하겠지만...
byte 배열을 사용한 이유는 0과 1로 나타내는 것이 가시성 있다고 판단하였기 때문.
이제 M x N 배열을 순회하며
모든 조각을 대조하고 max 값을 갱신하면 끝이다.
int max = 0;
// M x N 배열 순회
for(int m = 0; m < M; m++)
{
for(int n = 0; n < N; n++)
{
// 모든 조각 순회
for (int i = 0; i < 19; i++)
{
// max값 갱신
max = Math.Max(max, Sum(i, m, n));
}
}
}
// 조각 안의 숫자를 더하는 메서드
int Sum(int index, int m, int n)
{
int sum = 0;
for (int x = 0; x < 4; x++)
{
for (int y = 0; y < 4; y++)
{
// 조각의 해당 위치에 블럭이 없으면 continue
if (tetris[index, x, y] == 0)
continue;
// 조각이 M x N 배열의 범위를 넘어갔으면 0을 리턴한다.
if (m + x >= M || n + y >= N)
return 0;
// M x N 배열의 해당 위치에 있는 숫자를 더한다.
sum += arr[m + x, n + y];
}
}
return sum;
}
전체 코드
더보기
using System;
namespace BackjoonCodingTest
{
internal class Program
{
static void Main(string[] args)
{
using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());
string[] inputs = reader.ReadLine().Split();
int N = int.Parse(inputs[0]);
int M = int.Parse(inputs[1]);
short[,] arr = new short[M, N];
for(int i = 0; i < N; i++)
{
inputs = reader.ReadLine().Split();
for(int j = 0; j < M; j++)
{
arr[j, i] = short.Parse(inputs[j]);
}
}
byte[,,] tetris = {
{ {1, 1, 0, 0 },
{1, 1, 0, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 1, 1 },
{0, 0, 0, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 0, 0, 0 },
{1, 0, 0, 0 },
{1, 0, 0, 0 },
{1, 0, 0, 0 } } ,
{ {1, 0, 0, 0 },
{1, 0, 0, 0 },
{1, 1, 0, 0 },
{0, 0, 0, 0 } } ,
{ {0, 0, 1, 0 },
{1, 1, 1, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 0, 0 },
{0, 1, 0, 0 },
{0, 1, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 1, 0 },
{1, 0, 0, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {0, 1, 0, 0 },
{0, 1, 0, 0 },
{1, 1, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 1, 0 },
{0, 0, 1, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 0, 0 },
{1, 0, 0, 0 },
{1, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 0, 0, 0 },
{1, 1, 1, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 0, 0, 0 },
{1, 1, 0, 0 },
{0, 1, 0, 0 },
{0, 0, 0, 0 } } ,
{ {0, 1, 1, 0 },
{1, 1, 0, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {0, 1, 0, 0 },
{1, 1, 0, 0 },
{1, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 0, 0 },
{0, 1, 1, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {0, 1, 0, 0 },
{1, 1, 1, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {0, 1, 0, 0 },
{1, 1, 0, 0 },
{0, 1, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 1, 1, 0 },
{0, 1, 0, 0 },
{0, 0, 0, 0 },
{0, 0, 0, 0 } } ,
{ {1, 0, 0, 0 },
{1, 1, 0, 0 },
{1, 0, 0, 0 },
{0, 0, 0, 0 } } ,
};
int max = 0;
for(int m = 0; m < M; m++)
{
for(int n = 0; n < N; n++)
{
for (int i = 0; i < 19; i++)
{
max = Math.Max(max, Sum(i, m, n));
}
}
}
print.WriteLine(max);
int Sum(int index, int m, int n)
{
int sum = 0;
for (int x = 0; x < 4; x++)
{
for (int y = 0; y < 4; y++)
{
if (tetris[index, x, y] == 0)
continue;
if (m + x >= M || n + y >= N)
return 0;
sum += arr[m + x, n + y];
}
}
return sum;
}
reader.Close();
print.Close();
}
}
}반응형
'ProblemSolve' 카테고리의 다른 글
| [백준][C#] 1753 최단경로 - 골드4 (0) | 2023.07.12 |
|---|---|
| [백준][C#] 1504 특정한 최단 경로 - 골드4 (0) | 2023.07.12 |
| [백준][C#] 2293 동전 1 - 골드5 (1) | 2023.07.07 |
| [백준][C#] 1330 두 수 비교하기 - 브론즈5 (0) | 2023.07.07 |
| [백준][C#] 14503 로봇 청소기 - 골드5 (0) | 2023.07.07 |