Posts [백준] #17822 원판돌리기 Python (파이썬)
Post
Cancel

[백준] #17822 원판돌리기 Python (파이썬)

원판돌리기

문제링크

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퍼일지 모르겠네여 dequerotate를 쓰면 쉽게 풀 수 있는 문제이지 않을까 싶어요

  • dequerotate를 사용하여 회전해준다.
  • have_to_remove 의 빈 배열을 만들어 놓는다.
  • 먼저 같은 내의 원에서 인접한 애들이 있다면 해당 좌표를 have_to_removeappend한다.
  • 그다음 같은 내의 원이 아닌 인접한 원과 같은 상에 있는 좌표들 끼리 비교하여 값이 같으면 해당 좌표들을 have_to_removeappend한다.
  • 그리고 have_to_remove의 값들을 set을 통해 중복된 값을 제거한다.
  • have_to_remove 에 들어있는 좌표들의 값을 0 으로 만들어 준다.
  • 만약 have_to_remove 길이가 빈값이라면, 평균을 구한뒤 문제의 조건에 맞게 큰것은 -1 작은것은 +1 을해준다.
  • 테케를 다 돌고 최종 board의 합계를 출력한다

주의해야할 점은 원판에서 사라지는 값을 0으로 만들어 주었는데 인접한 수끼리 비교할때 0인 경우는 제외하고 계산해야합니다. 그리고, 평균을 구할때도 마찬가지로 0인 값은 빼주고 나눠야합니다.

This post is licensed under CC BY 4.0 by the author.

[백준] #20056 마법사 상어와 파이어볼 Python (파이썬)

[백준] #17143 낚시왕 python (파이썬)

Loading comments from Disqus ...