정보
문제 바로가기 [클릭]
난이도: Gold4
관련 개념: #구현 #시뮬레이션
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 1초 | 512 MB |
문제
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
- 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 Ar,c/5이고 소수점은 버린다.
- (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
- 공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
다음은 확산의 예시이다.
왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.
인접한 네 방향으로 모두 확산이 일어난다.
공기청정기가 있는 칸으로는 확산이 일어나지 않는다.
공기청정기의 바람은 다음과 같은 방향으로 순환한다.
방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.
입력
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
출력
첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.
예제 입출력 1
입력
1
2
3
4
5
6
7
8
7 8 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
출력
1
188
미세먼지의 확산이 일어나면 다음과 같은 상태가 된다.
공기청정기가 작동한 이후 상태는 아래와 같다.
예제 입출력 2
입력
1
2
3
4
5
6
7
8
7 8 2
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
출력
1
188
예제 입출력 3
입력
1
2
3
4
5
6
7
8
7 8 3
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
출력
1
186
예제 입출력 4
입력
1
2
3
4
5
6
7
8
7 8 4
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
출력
1
178
예제 입출력 5
입력
1
2
3
4
5
6
7
8
7 8 5
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
출력
1
172
예제 입출력 6
입력
1
2
3
4
5
6
7
8
7 8 20
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
출력
1
71
예제 입출력 7
입력
1
2
3
4
5
6
7
8
7 8 30
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
출력
1
52
예제 입출력 8
입력
1
2
3
4
5
6
7
8
7 8 50
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
출력
1
46
코드(파이썬)
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
import sys
r, c, t = map(int, sys.stdin.readline().split())
room = [list(map(int, sys.stdin.readline().split())) for _ in range(r)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
air_up, air_down = [i for i in range(r) if room[i][0]==-1]
for _ in range(t):
tmp_room = [[0] * c for _ in range(r)]
for x in range(r):
for y in range(c):
if x in [air_up, air_down] and y == 0:
continue
cnt = 0
for i in range(4):
d_x = x + dx[i]
d_y = y + dy[i]
if d_x in [air_up, air_down] and d_y == 0:
continue
if 0 <= d_x <= r-1 and 0 <= d_y <= c-1:
cnt += 1
tmp_room[x][y] += room[d_x][d_y] // 5
tmp_room[x][y] += room[x][y] - (room[x][y] // 5) * cnt
# 상단 반시계
# 왼쪽
for del_c in range(air_up-1, 0, -1):
tmp_room[del_c][0] = tmp_room[del_c-1][0]
# 위쪽
for del_r in range(0, c-1):
tmp_room[0][del_r] = tmp_room[0][del_r+1]
# 오른쪽
for del_c in range(0, air_up, 1):
tmp_room[del_c][c-1] = tmp_room[del_c+1][c-1]
# 아래쪽
for del_r in range(c-1, 1, -1):
tmp_room[air_up][del_r] = tmp_room[air_up][del_r-1]
tmp_room[air_up][1] = 0
# 하단 시계
# 왼쪽
for del_c in range(air_down+1, r-1):
tmp_room[del_c][0] = tmp_room[del_c+1][0]
# 아래쪽
for del_r in range(0, c-1):
tmp_room[r-1][del_r] = tmp_room[r-1][del_r+1]
# 오른쪽
for del_c in range(r-1, air_down, -1):
tmp_room[del_c][c-1] = tmp_room[del_c-1][c-1]
# 위쪽
for del_r in range(c-1, 1, -1):
tmp_room[air_down][del_r] = tmp_room[air_down][del_r-1]
tmp_room[air_down][1] = 0
room = tmp_room
print(sum([sum(row) for row in room]))
특이사항
- 문제의 조건에 따라 구현
- 같은 알고리즘이라도 현재 풀이는 pypy가 아닌 python3에서 시간초과가 발생하므로 시간복잡도를 줄여야 함
참고문헌
-
Comments powered by Disqus.