고정 헤더 영역
상세 컨텐츠
본문
https://www.acmicpc.net/problem/17406
17406번: 배열 돌리기 4
크기가 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)인 정사각형을 시계
www.acmicpc.net
내 풀이:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
N, M, K = map(int,input().split())
origin_arr = [list(map(int, input().split())) for _ in range(N)]
new_arr = [[0] * M for _ in range(N)]
rcs = []
answer = []
def rotation(r, c, s, arr):
global new_arr
for i in range(N):
for j in range(M):
new_arr[i][j] = arr[i][j]
for shell in range(1, s+1):
for x in range(2*shell):
new_arr[r-shell-1+x][c-shell-1] = arr[r-shell+x][c-shell-1]
for x in range(2*shell):
new_arr[r+shell-1][c-shell-1+x] = arr[r+shell-1][c-shell+x]
for x in range(2*shell):
new_arr[r+shell-1-x][c+shell-1] = arr[r+shell-2-x][c+shell-1]
for x in range(2*shell):
new_arr[r-shell-1][c+shell-1-x] = arr[r-shell-1][c+shell-2-x]
def sequence(index, K, table):
global answer
if index == K:
r = rcs[table[0]][0]
c = rcs[table[0]][1]
s = rcs[table[0]][2]
rotation(r, c, s, origin_arr)
for __ in range(1, K):
r = rcs[table[__]][0]
c = rcs[table[__]][1]
s = rcs[table[__]][2]
rotation(r, c, s, new_arr)
result = sum(new_arr[0])
for idx in range(1, N):
if result > sum(new_arr[idx]):
result = sum(new_arr[idx])
answer.append(result)
return
for _ in range(K):
if _ in table:
continue
table.append(_)
sequence(index+1, K, table)
table.remove(_)
for _ in range(K):
r, c, s = map(int, input().split())
rcs.append([r, c, s])
sequence(0, K, [])
print(min(answer))
|
Python3, 오답
샘플이 1개밖에 없는데 샘플은 정답이 나와서 아직 고민 중...
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
N, M, K = map(int,input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
new_arr = [[0] * M for _ in range(N)]
rcs = []
answer = []
for i in range(N):
for j in range(M):
new_arr[i][j] = arr[i][j]
def rotation(r, c, s, arr):
global new_arr
for i in range(N):
for j in range(M):
new_arr[i][j] = arr[i][j]
for shell in range(1, s+1):
for x in range(2*shell):
new_arr[r-1-shell][c-1-shell+1+x] = arr[r-1-shell][c-1-shell+x]
for x in range(2*shell):
new_arr[r-1-shell+1+x][c-1+shell] = arr[r-1-shell+x][c-1+shell]
for x in range(2*shell):
new_arr[r-1+shell][c-1+shell-1-x] = arr[r-1+shell][c-1+shell-x]
for x in range(2*shell):
new_arr[r-1+shell-1-x][c-1-shell] = arr[r-1+shell-x][c-1-shell]
def sequence(index, K, table):
global answer
if index == K:
r = rcs[table[0]][0]
c = rcs[table[0]][1]
s = rcs[table[0]][2]
rotation(r, c, s, arr)
for __ in range(1, K):
r = rcs[table[__]][0]
c = rcs[table[__]][1]
s = rcs[table[__]][2]
rotation(r, c, s, new_arr)
result = sum(new_arr[0])
for idx in range(1, N):
if result > sum(new_arr[idx]):
result = sum(new_arr[idx])
answer.append(result)
return
for _ in range(K):
if _ in table:
continue
table.append(_)
sequence(index+1, K, table)
table.remove(_)
for _ in range(K):
r, c, s = map(int, input().split())
rcs.append([r, c, s])
sequence(0, K, [])
print(min(answer))
|
Python3, 샘플 오답
잘못 작성했던 rotation함수를 내가 생각했던, 그리고 가독성이 좋게 수정하였다. 그러나 line 37의 rotation은 잘 돌아가는데 line 43의 rotation은 함수 내 new_arr와 arr가 메모리를 공유(shallow copy)되면서 원하는 결과를 출력하지 않았다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
N, M, K = map(int,input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
next_arr = [[0] * M for _ in range(N)]
rcs = []
answer = []
for i in range(N):
for j in range(M):
next_arr[i][j] = arr[i][j]
def rotation(r, c, s, arr):
new_arr = [[0] * M for _ in range(N)]
for i in range(N):
for j in range(M):
new_arr[i][j] = arr[i][j]
for shell in range(1, s+1):
for x in range(2*shell):
new_arr[r-1-shell][c-1-shell+1+x] = arr[r-1-shell][c-1-shell+x]
for x in range(2*shell):
new_arr[r-1-shell+1+x][c-1+shell] = arr[r-1-shell+x][c-1+shell]
for x in range(2*shell):
new_arr[r-1+shell][c-1+shell-1-x] = arr[r-1+shell][c-1+shell-x]
for x in range(2*shell):
new_arr[r-1+shell-1-x][c-1-shell] = arr[r-1+shell-x][c-1-shell]
return new_arr
def sequence(index, K, table):
global answer
if index == K:
r = rcs[table[0]][0]
c = rcs[table[0]][1]
s = rcs[table[0]][2]
next_arr = rotation(r, c, s, arr)
for __ in range(1, K):
r = rcs[table[__]][0]
c = rcs[table[__]][1]
s = rcs[table[__]][2]
next_arr = rotation(r, c, s, next_arr)
result = sum(next_arr[0])
for idx in range(1, N):
if result > sum(next_arr[idx]):
result = sum(next_arr[idx])
answer.append(result)
return
for _ in range(K):
if _ in table:
continue
table.append(_)
sequence(index+1, K, table)
table.remove(_)
for _ in range(K):
r, c, s = map(int, input().split())
rcs.append([r, c, s])
sequence(0, K, [])
print(min(answer))
|
Python3, 2100ms
전역 변수 new_arr를 제거하고 next_arr라는 변수를 새로 만들어서 메모리 공유하는 것을 방지하였다.
'Python > 문제풀이 (삼성 A형 대비)' 카테고리의 다른 글
| 파이썬으로 풀어보는 백준 17135번: 캐슬 디펜스 (삼성 A형 기출 문제) (0) | 2020.01.27 |
|---|---|
| 파이썬으로 풀어보는 백준 16637번: 괄호 추가하기 (삼성 A형 기출 문제) (2) | 2020.01.26 |
| 파이썬으로 풀어보는 백준 17471번: 게리맨더링 (삼성 A형 기출 문제) (0) | 2020.01.23 |
| 파이썬으로 풀어보는 SW Expert Academy 무선 충전 (삼성 A형 기출 문제) (0) | 2020.01.22 |
| 백준 17070번: 파이프 옮기기 1 (삼성 A형 기출 문제) (0) | 2020.01.18 |
댓글 영역