우주의 IT 소행성

1번째 풀이 / 메모리 초과

1 <= m , n <= 40000 거의 16억에 가까운 계산을 해야함. 메모리/시간 초과

# 메모리 초과 코드
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    m, n, tx, ty = map(int, input().split())
    year = []
    x, y = 1, 1
    while True:
        year.append((x, y))
        if x == m and y == n:
            break

        x += 1
        y += 1
        if x > m:
            x = 1
        if y > n:
            y = 1


    if (tx, ty) in year:
        ans = year.index((tx, ty)) + 1
        print(ans)
    else:
        print(-1)

2. 정답 코드

t = int(input())
for _ in range(t):
    m, n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    k = x
    while k < n * m:
        if k % n == y:
            print(k + 1)
            break
        k += m
    else:
        print(-1)

m = 5, n = 7이라고 했을 때

0 - 35까지의 테이블을 만들어보면

x = 0 ~ m -1 까지

y = 0 ~ n -1 까지 반복된다.

m, n, x, y 모든 값에서 1을 빼 나머지 연산을 가능하게 변환시킨다.

i번째 카잉 달력을  i: <i%M, i%N>

으로 나타낼 수 있다. 이를 통해

x과 3이고 y가 2일 경우  m, n 중 하나를 고정해둔다.

i : <i*M+3, y> 꼴로 두고

y가 2일 경우만 찾아주면 된다.

O(n)으로 해결.

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번의 반복문 속에서 미리 입력된 회전/대칭 도형들을 끼워맞춘다.

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

def check(matrix, start_row, end_row, start_col, end_col):
    n = len(matrix)
    ans = 1
    for i in range(start_row, end_row + 1):
        cnt = 1
        for j in range(1, n):
            if matrix[i][j] == matrix[i][j - 1]:
                cnt += 1
            else:
                cnt = 1
            if ans < cnt:
                ans = cnt
    for i in range(start_col, end_col + 1):
        cnt = 1
        for j in range(1, n):
            if matrix[j][i] == matrix[j - 1][i]:
                cnt += 1
            else:
                cnt = 1
            if ans < cnt:
                ans = cnt
    return ans


n = int(input())
matrix = [list(input()) for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if j + 1 < n:
            matrix[i][j], matrix[i][j + 1] = matrix[i][j + 1], matrix[i][j]
            temp = check(matrix, i, i, j, j + 1)
            if ans < temp:
                ans = temp
            matrix[i][j], matrix[i][j + 1] = matrix[i][j + 1], matrix[i][j]
        if i + 1 < n:
            matrix[i][j], matrix[i + 1][j] = matrix[i + 1][j], matrix[i][j]
            temp = check(matrix, i, i + 1, j, j)
            if ans < temp:
                ans = temp
            matrix[i][j], matrix[i + 1][j] = matrix[i + 1][j], matrix[i][j]
print(ans)

모든 matrix를 돌면서 우,하를 교체해주는 경우 O(N^2)

우 또는 하가 교체되었을 때 matrix의 변화를 살펴보면

상하 교체시 : 행2, 열1 영향

좌우 교체시 : 행1, 열2 영향

따라서 O(3N)이 소요

O(N^2) * O(3N) -> O(N^2) * O(N) -> O(N^3)

경우의수는 50개이므로 125,000 -> 통과 가능

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)의 코드로, 두 코드간 실행에는 큰 차이가 없음을 확인할 수 있었다.