14890. 경사로

https://www.acmicpc.net/problem/14890

14890번: 경사로

Solution

import sys
input = sys.stdin.readline

def chk(road, L, N):
    len = 0
    pre = road[0]
    for i, floor in enumerate(road):
        if floor == pre:
            len += 1
        elif abs(floor-pre) >= 2:
            return False
        elif floor > pre:
            if len < L:
                return False
            len = 1
        else: # floor < pre
            for j in range(L):
                if i+j >= N or road[i+j] != floor:
                    return False
            if i+L < N:
                if road[i+L-1] < road[i+L]:
                    return False
            len = -L+1
        pre = floor
    return True

n, L = map(int, input().split())
roads = []
for _ in range(n):
    roads.append(list(map(int, input().split())))

ans = 0
for road in roads:
    if chk(road, L, n):
        ans += 1

for i in range(n):
    a = [roads[j][i] for j in range(n)]
    if chk(a, L, n):
        ans += 1

print(ans)

• sys.stdin.readline를 이용해서 입력을 받는다.
• 각 row와 col을 뽑아내서 갈 수 있는 길인지 체크한다.
• 갈 수 있는 길이면 ans에 1을 더한다.

 

• 길을 하나씩 건너보면서 이전 땅과의 높이를 비교한다.
• 이전 땅과 높이가 같으면 len을 더해간다.
• 이전 땅과 높이가 2이상 차이나면 False를 반환한다.
• 이전 땅보다 높이가 높으면, 이전 땅이 연속해서 몇개가 같았는지 저장한 len과 L을 비교한다.
• 이전 땅보다 높이가 낮으면, 이후 L만큼의 같은 높이의 땅이 있는지 확인한다.
  • 같은 높이의 땅을 이후 for문에 계속 살피므로, len = -L+1로 설정한다.
  • 추가로 L만큼의 같은 높이의 땅이 있어도, 그 이후에 바로 나오는 땅이 높다면 False를 반환한다.(이거 없어도 len = -L+1 설정하는 것 때문에 괜찮다.)

• numpy를 사용하여 2차원 배열을 transpose를 하려 했지만, 백준에는 numpy 라이브러리를 import할 수 없다.
• else문에서 이후 L만큼의 같은 높이 땅이 있는 것을 알았다면, index를 증가시켜 그만큼의 for문을 돌지 않았으면 좋겠지만, python의 for문에서는 그게 안된다?