우주의 IT 소행성

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
score_board = [list(map(int, input().split())) for _ in range(n)]

tetrominos = [
    [(0, 1), (0, 2), (0, 3)],  # 가로 막대기
    [(1, 0), (2, 0), (3, 0)],  # 세로 막대기
    [(0, 1), (1, 0), (1, 1)],  # 네모
    [(1, 0), (2, 0), (2, 1)],  # 긴 ㄴ
    [(1, 0), (2, 0), (2, -1)],  # 긴 ㄴ 대칭 / 5
    [(0, 1), (0, 2), (1, 2)],  # ㄱ
    [(0, 1), (0, 2), (1, 0)],  # ㄱ 대칭
    [(0, 1), (1, 1), (2, 1)],  # 긴 ㄱ
    [(0, 1), (1, 0), (2, 0)],  # 긴 ㄱ 대칭
    [(0, 1), (0, 2), (-1, 2)],  # ㄴ 대칭 / 10
    [(1, 0), (1, 1), (1, 2)],  # ㄴ
    [(1, 0), (1, 1), (2, 1)],  # 선 ㄹ
    [(1, 0), (1, -1), (2, -1)],  # 선 ㄹ 대칭
    [(0, 1), (1, 0), (1, -1)],  # ㄹ 대칭
    [(0, 1), (1, 1), (1, 2)],  # ㄹ / 15
    [(0, 1), (0, 2), (1, 1)],  # ㅜ
    [(0, 1), (0, 2), (-1, 1)],  # ㅗ
    [(1, 0), (2, 0), (1, -1)],  # ㅓ
    [(1, 0), (2, 0), (1, 1)],  # ㅏ / 19
]

result = 0
for i in range(n):
    for j in range(m):
        for tetromino in tetrominos:
            flag = True
            score = score_board[i][j]
            for nx, ny in tetromino:
                x, y = nx + i, ny + j
                if 0 <= x < n and 0 <= y < m:
                    score += score_board[x][y]
                else:
                    flag = False
                    break
            if flag:
                if score > result:
                    result = score
print(result)

14500 테트로미노 풀이방법

일단 N * M 종이 위에 모든 종류의 테트로미노를 전부 놔 본다고 생각해보자.

일단 테트로미노의 종류를 구해야 할 것이다.

테트로미노는 회전과 대칭이 가능하므로

그림을 그려보면 다음과 같이 19종류의 테트로미노가 나온다.

각 테트로미노별로 N*M 배열에서 놓을 수 있는 경우의 수를 구해 시간복잡도를 구해보면

19 * O(3NM) 정도가 되는데, 결국 상수항은 제하고 O(NM)이 된다.

i, j = 0, 0

도형의 좌측 상단을 기준점으로 잡고 각 회전/대칭 도형의 칸별 좌표를 입력해주고

19번의 반복문 속에서 미리 입력된 회전/대칭 도형들을 끼워맞춘다.

맞출 때 마다 해당 칸의 수들의 최대값을 비교하여 작으면 해당 칸을 최대 값으로 갱신한다.

1. 9명의 난쟁이 중에서 7명을 찾는 방법

2. 9명의 난쟁이 중에서 2명을 찾는 방법

브루트포스로 문제를 해결할 수 있고,

itertools의 combinations을 사용해 문제를 해결할 수 있다.

#  combinations를 사용해 문제를 해결한 코드
from itertools import combinations
data = [int(input()) for _ in range(9)]

for i in combinations(data, 7):
    if sum(i) == 100:
        result = list(i)
        break

result.sort()
for i in result:
    print(i)

import sys
n = 9
a = [int(input()) for _ in range(n)]
a.sort()
for i in range(0, n):
    for j in range(i + 1, n):
        total = 0
        for k in range(0, n):
            if i == k or j == k:
                continue
            total += a[k]
        if total == 100:
            for k in range(0, n):
                if i == k or j == k:
                    continue
                print(a[k])
            sys.exit(0)

O(n^2)의 코드로, 두 코드간 실행에는 큰 차이가 없음을 확인할 수 있었다.

n, m = map(int, input().split())
data = [] # 초기 맵
temp = [[0] * m for _ in range(n)] # 벽을 설치한 맵

for _ in range(n):
    data.append(list(map(int, input().split())))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
result = 0

def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                virus(nx, ny)

def get_score():
    score = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                score += 1
    return score


def dfs(count):
    global result
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j]
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i, j)
        result = max(result, get_score())
        return

    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                count += 1
                dfs(count)
                data[i][j] = 0
                count -= 1

dfs(0)
print(result)

바이러스를 벽으로 어떻게 가두어야 제일 많은 안전 공간을 확보할 수 있냐의 문제이다.

주어진 벽은 총 3개, 맵의 크기는 8 * 8

총 64C3의 경우의 수를 모두 비교해 제일 많은 공간을 뽑아내면 된다.

비어있는 모든 공간에 3개의 벽을 설치하고, 그때마다의 안전 공간의 크기를 계산한 뒤 비교한다.

이렇게 연산하여 가장 많은 안전 공간을 출력해주면 된다.

BFS/DFS에 브루트포스가 함유된 알고리즘이었다.