문제링크
문제설명
반지름이 1,2,...,N인 원판이 반지름 작은 순으로 중심이 같게 놓여있다. 다음과 같이!
반지름 i인 원판은 i번째 원판이 되고, 각 원판에는 정수 M개가 써있다. (i,j)면 i번째 원판에 적힌 j번째 수가 되는 것이다.
이때, 인접의 조건은
(i,j) 기준
- 2<=i<=M-1 : (i-1,j) (i+1,j)
- i==N : (N-1,j)
- i==1 : (2,j)
- 2<=j<=N-1 : (i,j-1) (i,j+1)
- j==M : (i,M-1) (i,1)
- j==1 : (i,2) (i,M)
을 만족할때이다.
원판은 독립적으로 회전하고, 총 T번 번호가 x의 배수가 되는 원판을 방향 d(0:시계, 1:반시계)로 k만큼 회전시킨다.
회전을 마친 뒤 번호가 남아있으면 인접하고 같은 수를 찾는다.
이러한 수가 있으면 해당되는 수를 모두 지우고, 없으면 전체 평균을 구한 뒤, 평균보다 크면 -1, 작으면 +1을 해준다.
T번의 회전 뒤 모든 원판 위 수의 합을 구하라.
문제풀이
풀면서 설명이 빈약하다고 느꼈다. 특히 회전하고 지우는 부분,,,, 하나의 원판을 회전한 뒤 지우는지? 전체 원판 모두를 회전하고 지우는지? 평균은 한 원판 내에서 구하는지? 햇갈려서 일단 짜고 테케에 맞게 수정하느라 오래걸렸다 ^_ㅠ
결론적으로 i번째 회전을 모두 마치고 -> 인접하고 같은 수가 있는지? -> 있으면 지우기, 없으면 전체 원판 모두에 대한 평균치 구하고 값 갱신 이 정답이었다.
원판의 회전
원판의 회전은 직전에 푼 문제와 같은 로직으로 구현했다. 앞선 문제처럼 이어져있기때문에 (현재 idx+ 방향*이동거리)를 전체 idx갯수로 나눈 나머지가 idx가 된다.
def rotate(x, d, k):
before = copy.deepcopy(disk[x])
direction = 0
if d == 0:
direction = 1
else:
direction = -1
for i in range(len(before)):
ni = (i + direction * k) % M
disk[x][ni] = before[i]각 회전마다의 구현
각 회전마다
- 번호가 x의 배수인 원판을 d방향으로 k칸 회전시키기
for i in range(N):
if (i+1)%x == 0:
rotate(i, d, k)- 인접한 수 찾기
모든 원판 위의 수를 돌면서 인접한 수, 즉 지워야 할 수의 인덱스를total_adj = set()에 저장한다.
모든 원판 위의 수를 다 확인한 뒤, 지울 수가 있으면, 즉total_adj = set()에 원소가 두개 이상이면 해당 위치의 수를 0으로 만들어 지워준다.
없으면, 전체 원판의 수를 모두 더해 평균을 구하고, 조건에 맞게 값을 갱신해준다.
인접한 수에 대한 처리를 언제 해주느냐가 관건인듯 합니다,,
전체 코드
import sys
import copy
from collections import deque
input = sys.stdin.readline
N, M, K = map(int, input().split()) #N개의 원판 위에 M개의 숫자, K번 회전
disk = []
rotations = []
for _ in range(N):
disk.append(list(map(int, input().split())))
for _ in range(K):
# 번호가 x인 원판 d 방향으로 k칸 회전
rotations.append(list(map(int, input().split())))
def rotate(x, d, k):
before = copy.deepcopy(disk[x])
direction = 0
if d == 0:
direction = 1
else:
direction = -1
for i in range(len(before)):
ni = (i + direction * k) % M
disk[x][ni] = before[i]
for x, d, k in rotations:
# 1. 번호가 x의 배수인 원판을 d방향으로 k칸 회전시키기
for i in range(N):
if (i+1)%x == 0:
rotate(i, d, k)
# 2. 인접한 수 모두 찾기
total_adj = set()
for i in range(N):
for j in range(M):
same_adj = [(i,j)]
cur = disk[i][j]
if disk[i][j] == 0:
continue
# 인접한 10방향 전부 확인
else:
if i in range(1, N-1):
if disk[i-1][j] == cur:
same_adj.append((i-1,j))
if disk[i+1][j] == cur:
same_adj.append((i+1,j))
elif i == 0:
if disk[1][j] == cur:
same_adj.append((1,j))
elif i == N-1:
if disk[N-2][j] == cur:
same_adj.append((N-2,j))
if j in range(1, M-1):
if disk[i][j-1] == cur:
same_adj.append((i,j-1))
if disk[i][j+1] == cur:
same_adj.append((i,j+1))
elif j == M-1:
if disk[i][M-2] == cur:
same_adj.append((i,M-2))
if disk[i][0] == cur:
same_adj.append((i,0))
elif j == 0:
if disk[i][1] == cur:
same_adj.append((i,1))
if disk[i][M-1] == cur:
same_adj.append((i,M-1))
if len(same_adj) > 1:
for s in same_adj:
total_adj.add(s)
# 인접하고 같은 수가 있으면 지우기
if total_adj:
for t in total_adj:
disk[t[0]][t[1]] = 0
# 이번 회전에서 지워진게 없으면
else:
total = 0
cnt = 0
for i in range(N):
for j in range(M):
if disk[i][j] != 0:
total += disk[i][j]
cnt += 1
if cnt != 0:
avg = total/cnt
for i in range(N):
for j in range(M):
if disk[i][j] != 0:
if avg < disk[i][j]:
disk[i][j] -= 1
elif avg > disk[i][j]:
disk[i][j] += 1
else:
break
answer = 0
for i in range(N):
answer += sum(disk[i])
print(answer)
Hongik CE