이 조건들을 잘 따지면 정답을 구할 수 있다. (말은 쉽지만 이 문제 푸는데 아주 오래 걸렸다...)
이 문제를 푸는데 사용한 로직은 다음과 같다.
1. 같은 높이의 블럭이 나오면 갯수를 센다. (13~14번째 줄)
2. 다음 블럭의 높이가 2 이상 차이나면 조건을 위반하므로 flag를 False로 바꾼다. (29~31번째 줄)
3-1. 다음 블럭이 높을때, count와 경사로의 길이를 비교한다. count가 더 작으면 경사로를 놓을 수 없다는 의미이고, count가 경사로의 길이보다 같거나 더 크면 경사로를 놓을 수 있다는 의미이다. 그러므로 경사로를 놓고 count를 1로 초기화 시켜준다. (16~22번째 줄)
3-2. 다음 블럭이 낮을때, count를 0보다 같거나 큰 지 비교하고, 만약 그렇다면 경사로를 놓을 수 있다는 의미이므로 count를 -(경사로의 길이 - 1)로 설정한다. 아니면 앞에서 경사로를 놓는 도중 또 다른 낮은 블럭을 만났다는 의미이므로 경사로를 세울 수 없다. (23~28번째 줄)
4. 마지막으로, 만약 내려가는 경사로를 짓는 도중 길이 끝이 난다면, flag는 True이지만 count는 음수인 상태가 된다. 이를 확인해준다. (33~34번째 줄)
1~3번에 해당하는 로직들은 다음 그림을 통해 이해할 수 있다.
4번에 해당하는 로직의 예는 다음 그림을 통해 이해할 수 있다.
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
n, l = map(int, input().split())
board = [list(map(int, input().split())) for c inrange(n)]
board2 = list(list(r) for r in zip(*board))
answer =0
for i inrange(n):
# horizontal traverse
j, count =0, 1
flag = True
while j +1< n:
diff = abs(board[i][j] - board[i][j +1])
if diff ==0:
count +=1
elif diff ==1:
# uphill
if board[i][j] < board[i][j +1]:
# condition 4. it's too short to place a slope way
if count < l:
flag = False
else:
count =1
# downhill
else:
if count >=0:
count =-l +1
else:
flag = False
# condition 2. the difference is greater than 1
else:
flag = False
j +=1
if count >=0and flag:
answer +=1
# vertical traverse
j, count =0, 1
flag = True
while j +1< n:
diff = abs(board2[i][j] - board2[i][j +1])
if diff ==0:
count +=1
elif diff ==1:
# uphill
if board2[i][j] < board2[i][j +1]:
# condition 4. it's too short to place a slope way
