시간제한 1초
문제
밀렵꾼은 야간에 멧돼지 포획에 나섰다. 밀렵꾼이 있는 장소를 R*C의 격자판으로 표현할 수 있다. 각 격자칸에 멧돼지 정보가 주어지며, 밀렵꾼은 (R+1, 0) 부터 (R+1, C)까지 1초에 한 칸씩 움직인다. 움직일때마다 각 col 을 손전등으로 확인하고 눈 앞에 보이는 멧돼지 한 마리를 포획한다.
[그림 1]
멧돼지의 정보는 총 5가지로 이루어져있다. 멧돼지의 위치 y, x 와 멧돼지가 달리고 있는 방향 d, 달리는 속력 f, 멧돼지의 무게 w 이다. 멧돼지는 바라보는 방향 d를 향해 초당 f 칸 만큼 이동한다. 멧돼지가 이동한 후 같은 격자 칸에 2마리 이상의 멧돼지가 있을 경우 가장 무게가 많이 나가는 멧돼지가 다른 멧돼지들을 먹는다. [그림 1]의 멧돼지들의 정보는 [그림 2]에서 각 멧돼지 아래에 멧돼지 구분자, 속력, 크기 순서대로 적혀있다. [그림 3]은 [그림 2]에서 1초가 지난 뒤 모습이다. 멧돼지가 이동한 [그림 3] 모습 직후 밀렵꾼이 한 칸 이동하여 손전등을 비춰서 멧돼지를 확인한다. 보이는 멧돼지가 없기때문에 1초 후 포획되는 멧돼지는 없다.
[그림 2]
[그림 3]
[그림 4]
멧돼지의 정보가 주어졌을때, 포획된 멧돼지들의 무게 합을 구해보자. [그림 4] 이후 1초씩 지난 상황은 다음과 같다.
[그림 5]
[그림 6]
[그림 7]
[그림 8]
[그림 9]
[그림 10]
포획된 멧돼지의 무게 합은 10이다.
입력
첫 번째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 줄부터 T개의 테스트 케이스에 대한 정보가 주어진다. 각각의 테스트 케이스의 첫 번째 줄에 장소의 크기 R, C 와 멧돼지의 마릿수 M 이 공백을 통해 구분하여 주어진다. 두 번째 줄부터 M 개의 줄에 걸쳐 멧돼지 정보가 공백을 통해 구분하여 주어진다. 멧돼지의 위치 y, x 와 멧돼지가 달리고 있는 방향 d, 달리는 속력 f, 멧돼지의 무게 w 이다. 초기 멧돼지의 위치는 서로 겹치지 않으며, 같은 무게를 가진 멧돼지는 없다. 멧돼지가 달리고 있는 방향은 1부터 4까지의 정수이며, 숫자 순서대로 상하좌우를 의미한다. (3 ≤ R, C ≤ 100, 1 ≤ M ≤ R*C, 1 ≤ y ≤ R, 1 ≤ x ≤ C, 1 ≤ d ≤ 4, 0 ≤ f ≤ 1000, 1 ≤ w ≤ 10000)
출력
각 테스트 케이스에 대해 포획된 멧돼지의 무게 합을 출력한다. 각 테스트 케이스의 출력 양식은 "#t r"이다. t는 테스트 케이스의 번호이며, 1부터 시작한다. r은 문제에 대한 결과값을 뜻한다.
예제 입력
5
5 7 6
1 6 3 3 9
2 1 4 8 3
2 4 3 7 5
3 7 1 4 1
4 3 2 10 4
4 5 4 5 2
9 3 4
2 2 1 0 6
5 2 4 15 7
8 3 4 10 1
6 1 1 16 5
8 5 4
3 5 2 4 6
2 3 4 0 2
8 5 4 8 7
2 4 4 15 9
5 9 15
1 4 1 15 94
4 7 2 4 32
5 2 3 11 85
4 4 2 18 33
2 8 4 14 87
1 7 3 14 100
4 8 1 10 63
1 6 2 0 4
1 1 2 19 95
4 3 2 17 19
5 9 1 12 17
4 9 3 0 60
3 6 2 1 23
2 7 4 0 58
1 9 4 3 53
7 9 8
4 3 2 2 1
7 8 1 5 47
3 7 2 18 61
2 6 2 19 14
1 3 1 6 93
3 2 3 13 65
5 3 4 16 69
6 8 2 11 54
예제 출력
#1 10
#2 8
#3 16
#4 498
# 1차 풀이 틀림.. 답도 부정확하고, 시간초과 뜸
|
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
import sys
import copy
# 밀렵꾼은 (R+1, 0) 부터 (R+1, C)까지 1초에 한 칸씩 움직인다. -> 좌, 우로만 이동
# 움직일때마다 각 col 을 손전등으로 확인하고 눈 앞에 보이는 멧돼지 한 마리를 포획한다.
# 멧돼지의 정보는 총 5가지로 이루어져있다.
# 멧돼지의 위치 y, x 와 멧돼지가 달리고 있는 방향 d, 달리는 속력 f, 멧돼지의 무게 w 이다
# 멧돼지는 바라보는 방향 d를 향해 초당 f 칸 만큼 이동한다.
# 돼지가 이동한 후 같은 격자 칸에 2마리 이상의 멧돼지가 있을 경우
# 가장 무게가 많이 나가는 멧돼지가 다른 멧돼지들을 먹는다.
# 각 멧돼지 아래에 멧돼지 구분자, 속력, 크기 순서대로 적혀있다.
# 멧돼지가 이동한 [그림 3] 모습 직후 밀렵꾼이 한 칸 이동하여 손전등을 비춰서 멧돼지를 확인한다.
def get_next(cur, dist, max_size):
global d
while cur+dist<1 or cur+dist>max_size:
d = next_idx[d]
if cur+dist<1:
dist += cur-1
cur = 1
dist = -dist
elif cur+dist>max_size:
dist -= max_size - cur
cur = max_size
dist = -dist
return cur+dist
if __name__ == "__main__":
input = sys.stdin.readline
t = int(input())
for tt in range(t):
row, col, M = map(int, input().split())
# 1.멧돼지 셋팅 -> 초기 멧돼지의 위치는 서로 겹치지 않으며, 같은 무게를 가진 멧돼지는 없다.
pig_info = {}
getNum = 0
res_info = {}
catch_cnt = 0
# 2. pig_info를 초기 셋팅해준다.==============================================
for i in range(M):
yy, xx, dd, ff, ww = map(int, input().split())
temp_key = str(yy) + '/' + str(xx)
try:
pig_info[temp_key].append(yy)
pig_info[temp_key].append(xx)
pig_info[temp_key].append(dd)
pig_info[temp_key].append(ff)
pig_info[temp_key].append(ww)
except:
pig_info[temp_key]=list()
pig_info[temp_key].append(yy)
pig_info[temp_key].append(xx)
pig_info[temp_key].append(dd)
pig_info[temp_key].append(ff)
pig_info[temp_key].append(ww)
#print('first : ', pig_info)
# ============================================================================
for c in range(1, col+1):#포획
# 3. 이동한다.================================================================
for key, val in pig_info.items():
dy = [None, -1, 1, 0, 0]
dx = [None, 0, 0, -1, 1]
next_idx = [None, 2, 1, 4, 3]
y, x, d, f, w = val[0], val[1], val[2], val[3], val[4]
y = get_next(y, f*dy[d], row)
x = get_next(x, f*dx[d], col)
# 3-1. 변환된 좌표를 res_info에 넣어준다.
temp_key2 = str(y) + '/' + str(x)
try:
if res_info[temp_key2]:
if res_info[temp_key2][4] < w:
res_info[temp_key2][0] = y
res_info[temp_key2][1] = x
res_info[temp_key2][2] = d
res_info[temp_key2][3] = f
res_info[temp_key2][4] = w
except:
res_info[temp_key2] = list()
res_info[temp_key2].append(y)
res_info[temp_key2].append(x)
res_info[temp_key2].append(d)
res_info[temp_key2].append(f)
res_info[temp_key2].append(w)
# ============================================================================
# 4. 포획한다.(c의 값과 열이 같은 녀석들 제거)================================
pig_info = copy.deepcopy(res_info)
#print(res_info)
res_info = {}
temp_info_key = ''
temp_info_val = 0 #손전등과 최대한 가까운 행의 값을 가지고 있다
for kk, vv in pig_info.items():
if vv[1] == c:
if temp_info_val < vv[0]:
temp_info_key = kk
temp_info_val = vv[0]
if temp_info_val > 0:
catch_cnt += temp_info_val
del pig_info[temp_info_key]
temp_info_key = ''
temp_info_val = 0
# ============================================================================
print('#' + str(tt+1), catch_cnt)
|
cs |
#올바른 코드
|
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
# 밀렵꾼
import sys
# below has boar's y,x as key and d,f, w as value
global Boars
def move(lenAxis, cur, d, t, f):
# f칸 이동에 1초인 것을 기존 발견한 t 주기를 활용하기 위해
# 시간을 치환해서_1칸 f초_1칸 이동 1초 시 t 주기 활용
t =t*f
t %= (2*(lenAxis-1))
delta=[-1,1]
while( cur + t*delta[d] < 1 or cur + t*delta[d]> lenAxis):
if(cur + t*delta[d] < 1):
# next가 위쪽 범위 외가 되는 상황이라면, 딱 y-1칸 변화한 상황,
t -= (cur-1)
cur = 1
d=1
elif(cur + t*delta[d] > lenAxis):
t -= (lenAxis-cur)
cur = lenAxis
d=0
# 위 while 후 벽을 1번 또는 2번 찍은 직후 위치에서 남은 시간 만큼 이동
cur += t*delta[d]
return cur, d
def simulation(R,C,sec_th):
global Boars
# simulate boar's movement per sec, cuz this func is called per sec
# simulate poacher
time=1
cand_boars={}
keysBoar=Boars.keys()
for keyBoar in keysBoar:
# cur boar
r,c = keyBoar
d,f,w = Boars[keyBoar]
# print('cur boar ',r,c,d,f,w)
if( d < 2):
r, d=move(R,r,d,time,f)
else:
d-=2
c, d=move(C,c,d,time,f)
d+=2
# print('future ',r,c ,d)
# r,c means cur boar's candidate of future place
# if there is boar already, compare the w
if( (r,c) not in cand_boars.keys() ):
cand_boars[(r,c)]=(d,f,w)
else:
if(w>cand_boars[(r,c)][2]):
cand_boars[(r,c)]=(d,f,w)
else:
# cur boar is eaten
pass
Boars=cand_boars
# print(Boars)
# Now, Let simulate Poacher
# keysBoars=list(Boars.keys()) is same with below at py3
WeightPerSec=0
# 2마리 이상의 경우, 해당 초에 해당하는 열이고
# 동시에 Row가 제일 큰 한마리를 탐색해야함
# print('cur time', sec_th)
cand_keyboar = [keyBoar for keyBoar in list(Boars.keys()) if(keyBoar[1]==sec_th)]
# print('cand', cand_keyboar)
if(len(cand_keyboar)):
cand_keyboar = sorted(cand_keyboar, key=lambda x : x[0])
catchedboar= cand_keyboar[-1]
# print('keyBoar ',catchedboar,'is catched at sec_th ', sec_th)
WeightPerSec = Boars.pop(catchedboar)[2]
return WeightPerSec
if __name__=="__main__":
T=int(sys.stdin.readline().strip())
catchedWs=[]
for _ in range(1,T+1):
Boars={}
catchedW=0 # per Testcase
R,C,M = map(int,sys.stdin.readline().split())
# C also means t
time = C
for _ in range(M):
# y,x ; INDEX OF COMPUTER
y,x, d,f,w = map(int,sys.stdin.readline().split())
d -=1 # to make index
# 좌표의 중복이 없다고 한다.
Boars[(y,x)]=(d,f,w)
# print(Boars)
for sec in range(time):
sec_th=sec+1
catchedW+=simulation(R,C, sec_th)
# print(catchedW)
catchedWs.append(catchedW)
for num,val in enumerate(catchedWs,1):
print('#'+str(num),val)
|
cs |