[백준 #14890]: 경사로(python)

백준#14890:경사로

import sys

input = sys.stdin.readline
N, L = map(int, input().split())
runway = [list(map(int, input().split())) for _ in range(N)]

runway_check=[]
count=0
def check(way):
    for i in range(1,N):
        diff=way[i]-way[i-1]
        if(abs(diff)>1):
            return False
        if(diff==-1):
            for k in range(L):
                if(i+k>=N or runway_check[i+k] or way[i+k]!=way[i]):
                    return False
                runway_check[i+k]=True
        elif(diff==1):
            for k in range(L):
                if(i-k-1<0 or runway_check[i-k-1] or way[i-k-1]!=way[i-1]):
                    return False
                runway_check[i-k-1]=True
    return True

for i in runway:
    runway_check=[False] * N
    if check(i):
        count += 1

for i in range(N):
    runway_check=[False] * N
    if check([runway[j][i] for j in range(N)]):
        count += 1

print(count)

이 문제는 아이디어만 잘 생가각하면 쉽게 풀 수 있는 문제이다. 각각의 길을 들고와서 현재 블럭과 이전블럭을 비교한다. 만약 현재 블록과 이전블록의 차이가 1보다 크다면 경사로를 설치할 수 없으니 바로 끝낸다. 만약 -1 또는 1이라면 현재블록이 이전블록보다 작다는 것이니 경사로의 길이를 이용하여 설치여부를 판단하여주면 된다. 판단해주는 방식은 현재 위치에 경사로가 있는지 없는지와 이전의 블럭과 크기차이가 없는지 범위를 벗어나지 않았는지 검사하여 주면 된다.