17406번: 배열 돌리기 4
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의
www.acmicpc.net
문제
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.
1 2 3
2 1 1
4 5 6
배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.
예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.
A[1][1] A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
↑ ↓
A[2][1] A[2][2] A[2][3] → A[2][4] → A[2][5] A[2][6]
↑ ↑ ↓ ↓
A[3][1] A[3][2] A[3][3] A[3][4] A[3][5] A[3][6]
↑ ↑ ↓ ↓
A[4][1] A[4][2] A[4][3] ← A[4][4] ← A[4][5] A[4][6]
↑ ↓
A[5][1] A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]
A[6][1] A[6][2] A[6][3] A[6][4] A[6][5] A[6][6]
회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.
다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.
배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.
입력
첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.
둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.
출력
배열 A의 값의 최솟값을 출력한다.
제한
- 3 ≤ N, M ≤ 50
- 1 ≤ K ≤ 6
- 1 ≤ A[i][j] ≤ 100
- 1 ≤ s
- 1 ≤ r-s < r < r+s ≤ N
- 1 ≤ c-s < c < c+s ≤ M
코드
from collections import deque
from itertools import permutations
from copy import deepcopy
n, m, k = map(int, input().split())
arr = []
for _ in range(n):
arr.append(list(map(int, input().split())))
def rotate(r, c, s, arr_data):
for cnt in range(s): # s번의 정사각형 회전
top_r, top_c = r-s+cnt, c-s+cnt # 왼위
bottom_r, bottom_c = r+s-cnt, c+s-cnt # 오른아래
q = deque([])
# 왼줄
for i in range(top_r, bottom_r):
q.append(arr_data[i][top_c])
# 아랫줄
for i in range(top_c, bottom_c):
q.append(arr_data[bottom_r][i])
# 오른줄
for i in range(bottom_r, top_r, -1):
q.append(arr_data[i][bottom_c])
# 윗줄
for i in range(bottom_c, top_c, -1):
q.append(arr_data[top_r][i])
q.rotate(-1)
# 왼줄
for i in range(top_r, bottom_r):
arr_data[i][top_c] = q.popleft()
# 아랫줄
for i in range(top_c, bottom_c):
arr_data[bottom_r][i] = q.popleft()
# 오른줄
for i in range(bottom_r, top_r, -1):
arr_data[i][bottom_c] = q.popleft()
# 윗줄
for i in range(bottom_c, top_c, -1):
arr_data[top_r][i] = q.popleft()
cmd = []
for _ in range(k):
cmd.append(list(map(int, input().split())))
ans = 5001
for p in permutations(cmd, len(cmd)):
new_arr = deepcopy(arr)
for op in p: # p는 연산 순서 저장된 배열
rotate(op[0]-1, op[1]-1, op[2], new_arr)
for r in new_arr:
ans = min(ans, sum(r))
print(ans)

위 순서로 deque에 넣고 rotate(-1)로 왼쪽으로 한 칸씩 돌림
예를 들어 [8, 2, 4, 3, … , 3, 2 ] ⇒ [2, 4, 3, 2, … , 2, 8]
이렇게 된 배열을 다시 new_arr에 저장한다.
'문제풀이 > 구현' 카테고리의 다른 글
[Python/파이썬] 백준 21610번 마법사 상어와 비바라기 (0) | 2023.03.02 |
---|---|
[Python/파이썬] 백준 16927번 배열 돌리기 2 (0) | 2023.02.27 |
[Python/파이썬] 백준 16918번 봄버맨 (0) | 2023.02.25 |
[Python/파이썬] 백준 16926번 배열 돌리기 1 (0) | 2023.02.24 |
[Python/파이썬] 백준 15787번 기차가 어둠을 헤치고 은하수를 (0) | 2023.02.23 |
17406번: 배열 돌리기 4
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의
www.acmicpc.net
문제
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.
1 2 3 2 1 1 4 5 6
배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.
예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.
A[1][1] A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6] ↑ ↓ A[2][1] A[2][2] A[2][3] → A[2][4] → A[2][5] A[2][6] ↑ ↑ ↓ ↓ A[3][1] A[3][2] A[3][3] A[3][4] A[3][5] A[3][6] ↑ ↑ ↓ ↓ A[4][1] A[4][2] A[4][3] ← A[4][4] ← A[4][5] A[4][6] ↑ ↓ A[5][1] A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6] A[6][1] A[6][2] A[6][3] A[6][4] A[6][5] A[6][6]
회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.
다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.
배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.
입력
첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.
둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.
출력
배열 A의 값의 최솟값을 출력한다.
제한
- 3 ≤ N, M ≤ 50
- 1 ≤ K ≤ 6
- 1 ≤ A[i][j] ≤ 100
- 1 ≤ s
- 1 ≤ r-s < r < r+s ≤ N
- 1 ≤ c-s < c < c+s ≤ M
코드
from collections import deque from itertools import permutations from copy import deepcopy n, m, k = map(int, input().split()) arr = [] for _ in range(n): arr.append(list(map(int, input().split()))) def rotate(r, c, s, arr_data): for cnt in range(s): # s번의 정사각형 회전 top_r, top_c = r-s+cnt, c-s+cnt # 왼위 bottom_r, bottom_c = r+s-cnt, c+s-cnt # 오른아래 q = deque([]) # 왼줄 for i in range(top_r, bottom_r): q.append(arr_data[i][top_c]) # 아랫줄 for i in range(top_c, bottom_c): q.append(arr_data[bottom_r][i]) # 오른줄 for i in range(bottom_r, top_r, -1): q.append(arr_data[i][bottom_c]) # 윗줄 for i in range(bottom_c, top_c, -1): q.append(arr_data[top_r][i]) q.rotate(-1) # 왼줄 for i in range(top_r, bottom_r): arr_data[i][top_c] = q.popleft() # 아랫줄 for i in range(top_c, bottom_c): arr_data[bottom_r][i] = q.popleft() # 오른줄 for i in range(bottom_r, top_r, -1): arr_data[i][bottom_c] = q.popleft() # 윗줄 for i in range(bottom_c, top_c, -1): arr_data[top_r][i] = q.popleft() cmd = [] for _ in range(k): cmd.append(list(map(int, input().split()))) ans = 5001 for p in permutations(cmd, len(cmd)): new_arr = deepcopy(arr) for op in p: # p는 연산 순서 저장된 배열 rotate(op[0]-1, op[1]-1, op[2], new_arr) for r in new_arr: ans = min(ans, sum(r)) print(ans)

위 순서로 deque에 넣고 rotate(-1)로 왼쪽으로 한 칸씩 돌림
예를 들어 [8, 2, 4, 3, … , 3, 2 ] ⇒ [2, 4, 3, 2, … , 2, 8]
이렇게 된 배열을 다시 new_arr에 저장한다.
'문제풀이 > 구현' 카테고리의 다른 글
[Python/파이썬] 백준 21610번 마법사 상어와 비바라기 (0) | 2023.03.02 |
---|---|
[Python/파이썬] 백준 16927번 배열 돌리기 2 (0) | 2023.02.27 |
[Python/파이썬] 백준 16918번 봄버맨 (0) | 2023.02.25 |
[Python/파이썬] 백준 16926번 배열 돌리기 1 (0) | 2023.02.24 |
[Python/파이썬] 백준 15787번 기차가 어둠을 헤치고 은하수를 (0) | 2023.02.23 |