https://www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
# 20057 마법사 상어와 토네이도
# 좌 하 우 상
dr = [0, 1, 0, -1]
dc = [-1, 0, 1, 0]
def tornado(cur_r, cur_c, cur_dir):
plus_gr = list()
cur_dust = grounds[cur_r][cur_c]
total_spend_dust = 0
total_outside_dust = 0
## 5% 앞앞 ##
go_two_r = cur_r + (dr[cur_dir]) * 2
go_two_c = cur_c + (dc[cur_dir]) * 2
dust = cur_dust * 5 // 100
# 범위 안에 있다면
if 0 <= go_two_r < N and 0 <= go_two_c < N:
total_spend_dust += dust
plus_gr.append([go_two_r, go_two_c, dust])
# 범위 밖이라면
else:
total_outside_dust += dust
## 10% 앞 왼쪽 ##
go_one_r = cur_r + dr[cur_dir]
go_one_c = cur_c + dc[cur_dir]
# 좌 -> 아래로
cur_dir2 = (cur_dir + 1) % 4
go_left_r = go_one_r + dr[cur_dir2]
go_left_c = go_one_c + dc[cur_dir2]
dust = cur_dust * 10 // 100
# 범위 안에 있다면
if 0 <= go_left_r < N and 0 <= go_left_c < N:
total_spend_dust += dust
plus_gr.append([go_left_r, go_left_c, dust])
# 범위 밖이라면
else:
total_outside_dust += dust
## 10% 앞 오른쪽 ##
# 우 -> 위로
cur_dir2 = (cur_dir - 1) % 4
go_right_r = go_one_r + dr[cur_dir2]
go_right_c = go_one_c + dc[cur_dir2]
dust = cur_dust * 10 // 100
# 범위 안에 있다면
if 0 <= go_right_r < N and 0 <= go_right_c < N:
total_spend_dust += dust
plus_gr.append([go_right_r, go_right_c, dust])
# 범위 밖이라면
else:
total_outside_dust += dust
## 7% 왼쪽 ##
cur_dir2 = (cur_dir + 1) % 4
go_left_r = cur_r + dr[cur_dir2]
go_left_c = cur_c + dc[cur_dir2]
dust = cur_dust * 7 // 100
# 범위 안에 있다면
if 0 <= go_left_r < N and 0 <= go_left_c < N:
total_spend_dust += dust
plus_gr.append([go_left_r, go_left_c, dust])
# 범위 밖이라면
else:
total_outside_dust += dust
## 2% 왼왼쪽 ##
go_left_left_r = cur_r + (dr[cur_dir2] * 2)
go_left_left_c = cur_c + (dc[cur_dir2] * 2)
dust = cur_dust * 2 // 100
# 범위 안에 있다면
if 0 <= go_left_left_r < N and 0 <= go_left_left_c < N:
total_spend_dust += dust
plus_gr.append([go_left_left_r, go_left_left_c, dust])
# 범위 밖이라면
else:
total_outside_dust += dust
## 1% 왼쪽의 왼쪽 ##
cur_dir2 = (cur_dir2 + 1) % 4
go_left_r = go_left_r + dr[cur_dir2]
go_left_c = go_left_c + dc[cur_dir2]
dust = cur_dust * 1 // 100
# 범위 안에 있다면
if 0 <= go_left_r < N and 0 <= go_left_c < N:
total_spend_dust += dust
plus_gr.append([go_left_r, go_left_c, dust])
# 범위 밖이라면
else:
total_outside_dust += dust
## 7% 오른쪽 ##
cur_dir2 = (cur_dir - 1) % 4
go_right_r = cur_r + dr[cur_dir2]
go_right_c = cur_c + dc[cur_dir2]
dust = cur_dust * 7 // 100
# 범위 안에 있다면
if 0 <= go_right_r < N and 0 <= go_right_c < N:
total_spend_dust += dust
plus_gr.append([go_right_r, go_right_c, dust])
# 범위 밖이라면
else:
total_outside_dust += dust
## 2% 오른오른쪽 ##
go_right_right_r = cur_r + (dr[cur_dir2] * 2)
go_right_right_c = cur_c + (dc[cur_dir2] * 2)
dust = cur_dust * 2 // 100
# 범위 안에 있다면
if 0 <= go_right_right_r < N and 0 <= go_right_right_c < N:
total_spend_dust += dust
plus_gr.append([go_right_right_r, go_right_right_c, dust])
# 범위 밖이라면
else:
total_outside_dust += dust
## 1% 오른쪽의 오른쪽 ##
cur_dir2 = (cur_dir2 - 1) % 4
go_right_r = go_right_r + dr[cur_dir2]
go_right_c = go_right_c + dc[cur_dir2]
dust = cur_dust * 1 // 100
# 범위 안에 있다면
if 0 <= go_right_r < N and 0 <= go_right_c < N:
total_spend_dust += dust
plus_gr.append([go_right_r, go_right_c, dust])
# 범위 밖이라면
else:
total_outside_dust += dust
# y값의 먼지 없애기
grounds[cur_r][cur_c] = 0
# alpha 구하기
alpha = cur_dust - total_spend_dust - total_outside_dust
cr = cur_r + dr[cur_dir]
cc = cur_c + dc[cur_dir]
# 범위 안에 있다면
if 0 <= cr < N and 0 <= cc < N:
plus_gr.append([cr, cc, alpha])
else:
total_outside_dust += alpha
alpha = 0
# 각 칸에 dust 더해주기
for temp_r, temp_c, temp_dust in plus_gr:
grounds[temp_r][temp_c] += temp_dust
return total_outside_dust
N = int(input())
grounds = [list(map(int, input().split())) for _ in range(N)]
result = 0
cur_r = N // 2
cur_c = N // 2
cur_dir = 0
cur_cnt = 1
while cur_c >= 0:
for _ in range(cur_cnt):
# 좌/우
cur_r = cur_r + dr[cur_dir]
cur_c = cur_c + dc[cur_dir]
if cur_c < 0:
break
cur_score = tornado(cur_r, cur_c, cur_dir)
result += cur_score
if cur_c < 0:
break
cur_dir = (cur_dir + 1) % 4
for _ in range(cur_cnt):
# 하/상
cur_r = cur_r + dr[cur_dir]
cur_c = cur_c + dc[cur_dir]
if cur_c < 0:
break
cur_score = tornado(cur_r, cur_c, cur_dir)
result += cur_score
if cur_c < 0:
break
cur_dir = (cur_dir + 1) % 4
# 횟수 증가
cur_cnt += 1
print(result)
"""
시간 초과
plus_gr을 넣어줄 때, N * N 배열로 만들어주니 시간초과가 났다.
맞왜틀의 연속.. 의심..
찾다찾다 못찾아서, 예전에 맞춘 기록과 시간초과가 났던 기록을 비교했다.
plus_gr을 초기화시켜서 받는 게 아니라, 해당하는 r, c값이 나오면 그 r, c 값과 dust 값을 따로 저장해주는 방식을 사용했다.
아.... 똑같이 틀렸던 것을 또 틀렸다. 흑흑
"""
예전 코드
# 20057 마법사 상어와 토네이도
def tornado(r, c, direction):
out_value = 0
temp_grounds = list()
dir1 = direction
dir2 = dir1 + 1
dir3 = dir1 + 2
dir4 = dir1 + 3
dir2 %= 4
dir3 %= 4
dir4 %= 4
cur_value = grounds[r][c]
count_dirt = 0
value1 = cur_value * 1 // 100
value2 = cur_value * 2 // 100
value5 = cur_value * 5 // 100
value7 = cur_value * 7 // 100
value10 = cur_value * 10 // 100
# 좌측 기준
# 위 한 칸
cr = r + dr[dir2]
cc = c + dc[dir2]
if 1 <= cr <= N and 1 <= cc <= N:
temp_grounds.append([cr, cc, value7])
else:
out_value += value7
count_dirt += value7
# 위 앞칸
kr = cr + dr[dir1]
kc = cc + dc[dir1]
if 1 <= kr <= N and 1 <= kc <= N:
temp_grounds.append([kr, kc, value10])
else:
out_value += value10
count_dirt += value10
# 위 뒤칸
kr = cr + dr[dir3]
kc = cc + dc[dir3]
if 1 <= kr <= N and 1 <= kc <= N:
temp_grounds.append([kr, kc, value1])
else:
out_value += value1
count_dirt += value1
# 위 위 칸
kr = cr + dr[dir2]
kc = cc + dc[dir2]
if 1 <= kr <= N and 1 <= kc <= N:
temp_grounds.append([kr, kc, value2])
else:
out_value += value2
count_dirt += value2
# 아래 한 칸
cr = r + dr[dir4]
cc = c + dc[dir4]
if 1 <= cr <= N and 1 <= cc <= N:
temp_grounds.append([cr, cc, value7])
else:
out_value += value7
count_dirt += value7
# 아래 앞칸
kr = cr + dr[dir1]
kc = cc + dc[dir1]
if 1 <= kr <= N and 1 <= kc <= N:
temp_grounds.append([kr, kc, value10])
else:
out_value += value10
count_dirt += value10
# 아래 뒤칸
kr = cr + dr[dir3]
kc = cc + dc[dir3]
if 1 <= kr <= N and 1 <= kc <= N:
temp_grounds.append([kr, kc, value1])
else:
out_value += value1
count_dirt += value1
# 아래 아래 칸
kr = cr + dr[dir4]
kc = cc + dc[dir4]
if 1 <= kr <= N and 1 <= kc <= N:
temp_grounds.append([kr, kc, value2])
else:
out_value += value2
count_dirt += value2
# 앞 앞칸
cr = r + dr[dir1] * 2
cc = c + dc[dir1] * 2
if 1 <= cr <= N and 1 <= cc <= N:
temp_grounds.append([cr, cc, value5])
else:
out_value += value5
count_dirt += value5
# 바로 앞칸
cr = r + dr[dir1]
cc = c + dc[dir1]
temp_vaiue = cur_value - count_dirt
if 1 <= cr <= N and 1 <= cc <= N:
temp_grounds.append([cr, cc, temp_vaiue])
else:
out_value += temp_vaiue
grounds[r][c] = 0
for tr, tc, t_value in temp_grounds:
grounds[tr][tc] += t_value
return out_value
# 좌 하 우 상
dr = [0, 1, 0, -1]
dc = [-1, 0, 1, 0]
N = int(input())
grounds = [[0] * (N + 1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
temp_r = N // 2 + 1
temp_c = N // 2 + 1
result = 0
# 한 칸씩 움직임
num = 1
direction = 0
while 0 < temp_r <= N and 0 < temp_c <= N:
direction %= 4
for _ in range(num):
temp_r += dr[direction]
temp_c += dc[direction]
if temp_c == 0 or temp_r == 0:
break
# 토네이도 작업
result += tornado(temp_r, temp_c, direction)
direction += 1
if direction % 2 == 0:
num += 1
print(result)
'프로그래밍 > 문제풀이' 카테고리의 다른 글
| [Python] 백준 21609 상어 중학교 (0) | 2022.10.13 |
|---|---|
| [Python] 백준 21608 상어 초등학교 (0) | 2022.10.12 |
| [Python] 코드트리 2022-1 오전 술래잡기 (0) | 2022.10.10 |
| [Python] 백준 17143 낚시왕 (0) | 2022.10.09 |
| [Python] 백준 20058 마법사 상어와 파이어볼 (0) | 2022.10.08 |
