원판돌리기
문제링크
https://www.acmicpc.net/problem/17822
코드
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
71
72
73
74
75
76
77
import sys
from collections import deque
sys.stdin = open("input.txt",'r')
n,m,t = map(int,input().split()) #원판의 개수, 원판에 적힌 정수의 개수, T 번 회전
board = [deque(int(x) for x in input().split()) for _ in range(n)]
info = [[int(x) for x in input().split()] for _ in range(t)] # x배수, d 방향, k 칸 회전
# d == 0 시계 방향 d == 1 반시계 방향
for tc in range(t):
x,d,k = info[tc]
# 회전하기
result = 0
for i in range(n):
result += sum(board[i])
if (i+1)%x == 0:
if d == 0:
board[i].rotate(k)
else:
board[i].rotate(-k)
# 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다
if result != 0:
#그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
have_to_remove = []
# 먼저 같은 원내에서 인접한 애들
for i in range(n):
for j in range(m-1):
if board[i][j] != 0 and board[i][j+1] != 0 and board[i][j] == board[i][j+1]:
have_to_remove.append((i,j))
have_to_remove.append((i,j+1))
if board[i][0] != 0 and board[i][-1]!=0 and board[i][0] == board[i][-1]:
have_to_remove.append((i,0))
have_to_remove.append((i,m-1))
# 옆의 원
for j in range(m):
for i in range(n-1):
if board[i][j] != 0 and board[i+1][j] != 0 and board[i][j] == board[i+1][j]:
have_to_remove.append((i,j))
have_to_remove.append((i+1,j))
# 원판 다시 만들어주기
have_to_remove = list(set(have_to_remove))
for i in range(len(have_to_remove)):
x,y = have_to_remove[i]
board[x][y] = 0
#없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.
if len(have_to_remove) == 0:
avg_sum = 0
zero_cnt = 0
for i in range(n):
avg_sum += sum(board[i])
zero_cnt += board[i].count(0)
avg = avg_sum / (n*m-zero_cnt)
for i in range(n):
for j in range(m):
if board[i][j] != 0 and board[i][j] > avg:
board[i][j] -= 1
elif board[i][j] !=0 and board[i][j] < avg:
board[i][j] += 1
else:
break
ans = 0
for i in range(n):
ans += sum(board[i])
print(ans)
풀이
이문제 왜 정답률이 29퍼일지 모르겠네여 deque
의 rotate
를 쓰면 쉽게 풀 수 있는 문제이지 않을까 싶어요
deque
의rotate
를 사용하여 회전해준다.have_to_remove
의 빈 배열을 만들어 놓는다.- 먼저 같은 내의 원에서 인접한 애들이 있다면 해당 좌표를
have_to_remove
에append
한다. - 그다음 같은 내의 원이 아닌 인접한 원과 같은 열상에 있는 좌표들 끼리 비교하여 값이 같으면 해당 좌표들을
have_to_remove
에append
한다. - 그리고
have_to_remove
의 값들을set
을 통해 중복된 값을 제거한다. have_to_remove
에 들어있는 좌표들의 값을 0 으로 만들어 준다.- 만약
have_to_remove
길이가 빈값이라면, 평균을 구한뒤 문제의 조건에 맞게 큰것은 -1 작은것은 +1 을해준다. - 테케를 다 돌고 최종 board의 합계를 출력한다
주의해야할 점은 원판에서 사라지는 값을 0으로 만들어 주었는데 인접한 수끼리 비교할때 0인 경우는 제외하고 계산해야합니다. 그리고, 평균을 구할때도 마찬가지로 0인 값은 빼주고 나눠야합니다.