문제
https://www.acmicpc.net/problem/21277
접근
- 카카오 기출 문제 중 자물쇠와 열쇠 문제에서 힌트를 얻어, 기준 퍼즐1의 범위를 확장 시켜서 전체 경우마다 퍼즐2와 맞춰보는 식으로 풀이했다.
- 퍼즐의 크기 제한이 50 이므로 상하좌우 50씩 확장할 경우, 최대로 확장될 수 있는 퍼즐의 한 변의 길이는 150이다.
- 따라서 회전까지 고려했을 때 최대 4 * 100 * 100 * 50 * 50 = 10 * 9 번의 연산이 발생하므로 제한시간 2초 이내에 풀 수 있을 것
- 또한 퍼즐2를 회전시킬 때마다 r과 c가 변하므로 r과 c를 바꿔주는 작업을 해주어야 한다.
풀이
- 퍼즐1에 대해 상하좌우 50씩 확장시키고, 가능한 모든 경우에 대해 맞출 수 있는지 또한 맞출 수 있다면 그때의 크기가 얼마인지 계산한다.
- 퍼즐을 맞춘 결과를 구하는 것이 아니므로, 퍼즐을 맞췄다가 안되는 경우 다시 빼는 과정을 반복할 필요 없이 주어진 퍼즐이 맞출 수 있는 경우라면 x와 y의 최댓값과 최솟값만 계산해서 넓이를 구한다.
def rotate():
global r, c
res = [[0] * len(b) for _ in range(len(b[0]))]
for i in range(len(b[0])):
for j in range(len(b)):
res[i][j] = b[j][len(b[0]) - i - 1]
r, c = c, r
return res
def match(x, y):
global ans
check = False
for i in range(x, x + len(b)):
for j in range(y, y + len(b[0])):
if b[i - x][j - y] == 1 and board[i][j] == 1:
check = True
break
if check:
break
if not check:
min_x = min(x, 50)
min_y = min(y, 50)
max_x = max(x + r - 1, 50 + n - 1)
max_y = max(y + c - 1, 50 + m - 1)
s = (max_x - min_x + 1) * (max_y - min_y + 1)
if ans == -1 or s < ans:
ans = s
n, m = map(int, input().split())
a = [list(map(int, list(input()))) for _ in range(n)]
r, c = map(int, input().split())
b = [list(map(int, list(input()))) for _ in range(r)]
board = [[0] * (m + 2 * 50) for _ in range(n + 2 * 50)]
for i in range(50, 50 + n):
for j in range(50, 50 + m):
board[i][j] = a[i - 50][j - 50]
ans = -1
for _ in range(4):
b = rotate()
for i in range(50 + n):
for j in range(50 + m):
match(i, j)
print(ans)
'Python > Coding Test' 카테고리의 다른 글
1863 스카이라인 쉬운거 (0) | 2022.02.26 |
---|---|
20182 골목 대장 호석 - 효율성 1 (0) | 2022.02.25 |
10703 유성 (0) | 2022.02.24 |
13168 내일로 여행 (0) | 2022.02.23 |
1421 나무꾼 이다솜 (0) | 2022.02.23 |