경사로 (14890번) - 백준 (BOJ)

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

14890번: 경사로

 

백준 - 경사로 (14890번)

 

난이도 : Gold 3

알고리즘 : Simulation

풀이 소요 시간 : 55분

문제집 : 삼성 SW 역량 테스트 기출 문제

 

import sys
input = sys.stdin.readline


def calc_row(row):
    cur = row[0]
    acc = L
    for h in row:
        if cur == h:  # 1
            acc += 1
        elif cur+1 == h:  # 2
            if acc < L2:
                return 0
            acc = L+1
        elif cur == h+1:  # 3
            if acc < L:
                return 0
            acc = 1
        else:  # 4
            return 0
        cur = h
    return 0 if acc < L else 1


if __name__ == '__main__':
    N, L = map(int, input().split())
    L2 = L<<1
    board = [list(map(int, input().split())) for _ in range(N)]
    cnt = sum(calc_row(row) for row in board)
    cnt += sum(calc_row(list(row)) for row in zip(*board))
    print(cnt)

 

한 행 (row)을 순서대로 탐색하면서, 현재 높이 (cur)와 다음 높이 (h) 를 비교한다.

1. h와 cur의 높이가 같다면 (cur == h),

    cur의 연속 등장 횟수 (acc)에 1을 더해준다.

2. h가 cur보다 한 칸 높거나 (cur+1 == h),

3. h가 cur보다 한 칸 낮다면 (cur == h+1),

    경사로를 놓을 수 있을만큼 충분한 공간 (acc) 이 있는지 확인한다.

    공간이 있다면 경사로를 놓고,

    공간이 부족하다면 지나갈 수 없는 길이므로, 0을 return 한다.

4. 그 외의 경우에는 지나갈 수 없는 길이므로, 0을 return 한다.