[백준 14890] 경사로(Python)

1.아이디어

문제의 요구사항대로 구현하면된다. 문제의 조건을 만족한다고 가정할 때, 낮은 값이 왼쪽에 있을 때와 오른쪽에 있을 때, 연속적으로 동일한 낮은 값을 갖는 원소 수를 세는 방법이 서로 다르다. 짧게 설명을 하면, 낮은 값이 왼쪽에 있을 때는 원소 수를 1증가 시키고, 다음 재귀함수로 넘어간다. 그외 별도의 처리는 없다. 낮은 값이 오른쪽에 있을 때는 반복문을 이용해 l개의 연속적으로 동일한 낮은 값을 갖는 원소를 갖는지 확인한다. 다시말해, 한번에 하나씩 세는 방법이 낮은 값이 왼쪽에 있을 때이고, 한번에 임의의 수만큼 세는 방법이 낮은 값이 오른쪽에 있을 때이다.

높은 값과 낮은 값을 알아내는 방법은 이전 값과 현재 값을 비교하면 쉽게 알아낼 수 있고, 그 외 부분은 문제 지문에서 조건이 잘 설명되어있어서, 이를 보면서 풀면된다.

2.코드

import sys

n, l = map(int, sys.stdin.readline().rsplit())
arr = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(n)]
answer = 0

def solve(y, x, val, cnt):
    if x == n: return True
    if arr[y][x] == val: cnt += 1
    elif abs(arr[y][x]-val) > 1: return False
    elif val < arr[y][x]:
        if cnt < l: return False
        val = arr[y][x]
        cnt = 1
    
    elif val > arr[y][x]:
        k = 0
        cnt = 0
        for k in range(x, n):
            if arr[y][k] == arr[y][x]: cnt += 1
            else: break

            if cnt == l: break

        val = arr[y][x]
        if cnt < l: return False
        x = k
        cnt = 0
    
    return solve(y, x+1, val, cnt)

for i in range(n):
    if solve(i, 1, arr[i][0], 1): answer += 1
    
arr = [[arr[j][i] for j in range(n)] for i in range(n)]
for i in range(n):
    if solve(i, 1, arr[i][0], 1): answer += 1

print(answer)