우주의 IT 소행성

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에 브루트포스가 함유된 알고리즘이었다.

주어진 범위 내에서 소수를 찾아, 그 소수들의 합과 최소값을 가지는 소수를 출력하는 문제이다.

에라토스테네스의 체 알고리즘을 이용하여 소수를 구해주면 된다.

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

1) 2부터 N까지 모든 자연수를 나열

2) 남은 수 중 아직 처리하지 않은 가장 작은 수 i를 찾는다.

3) 남은 수 중에서 i의 배수를 모두 제거한다.

4) 더이상 반복할 수 없을 때 까지 2, 3을 반복

시간 복잡도는 O(NloglogN)으로 선형 시간에 필적할 수준.

하지만 메모리를 많이 잡아먹는 단점이 있으니 잘 확인해보아야 한다.

이 문제를 보자마자, 아 permutation을 써서 나올 수 있는 모든 경우의 수중 30으로 나누어 떨어지는 수의

최대 값이 정답이겠구나! 라는 생각이 들어 코드를 짜보았으나.. 결과는 시간초과였다.

from itertools import permutations
n = input()
data = []

for i in permutations(n, len(n)):
    tmp = int("".join(i))
    if tmp % 30 == 0:
        data.append(tmp)

if data:
    print(max(data))
    exit()

print("-1")

시간 초과가 된 코드는 바로 이것인데, 순열의 경우의 수가 10^5 까지 간다면, 그만큼 시공간 복잡도의 수가 기하급수적으로 늘어나게 됨을 간과하였다.

문제를 다시 곰곰히 살펴보니, 30의 배수가 되는 가장 큰 수 를 만들라는게 제일 큰 힌트였다.

30의 배수 -> 3의 배수 이면서 10의 배수.

결국 최대 값이면서, 맨 오른쪽 끝이 0으로 끝나야하니

입력받은 값을 역순으로 정렬하여 그 값이 30으로 나누어 떨어지기만 하면 되는 것이다.

n = list(input())
n.sort(reverse = True)
n = int("".join(n))
if n % 30 == 0:
    print(n)
else:
    print("-1")

이렇게 쉽게 풀수 있었던 걸 너무 고전하였던 것 같다.

문제를 잘 읽어보는 습관을 들이자.