김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 14890 경사로 파이썬(Python)

문제 링크

보드 위를 조건에 맞게 순회하는 구현 문제.
경사로를 설치하는 조건이 조금 까다로운데, 내 풀이의 경우 이를 쿨타임으로 구현했다.
쿨타임은 up_cooltime과 down_cooltime이 있는데, 말 그대로 각각 올라가는, 내려가는 경사로를 설치하는 데에 필요한 쿨타임(칸의 수)이다.
쿨타임은 한 칸마다 1씩 줄어들며, 쿨타임이 남아있는 동안 경사로를 설치하는 것이 불가능하므로 경사로를 설치해야 할 때 쿨타임이 있다면 그 길은 지나갈 수 없는 길이다.
그렇다면 쿨타임은 어떤 경우 얼마나 발생하는가?
처음에는 up = l; down = 0으로 초기화한다. 시작하고 나서 l개의 칸이 있어야 올라가는 경사로를 설치할 수 있고, 내려가는 경사로는 바로 설치할 수 있기 때문이다.
올라가는 경사로를 설치한 경우 높이가 바뀌었으므로 l개의 칸이 있어야 올라가는 경사로를 또 설치할 수 있다. 즉 up = l로 갱신된다.
하지만 올라가는 경사로를 설치하고 바로 내려가는 경사로를 설치해도 문제가 없으므로 down은 값이 바뀌지 않는다.
내려가는 경사로를 설치한 경우 뒤 l칸 동안 경사로의 높낮이가 바뀌지 않아야 한다. 따라서 up과 down이 모두 l로 갱신된다.
그런데, 올라가는 경사로의 경우 내려가는 경사로랑 겹쳐 놓을 수 없기 때문에 내려가는 경사로를 놓은 뒤 l칸이 더 필요하다. 따라서 up은 추가로 l의 쿨타임이 발생해 최종적으로 l * 2가 된다.
이제 모든 경우를 확인했으니 구현하면 된다. 주의해야 할 점은 내려가는 경사로의 쿨타임이 남아있는데 보드가 끝나는 경우이다.
이때는, 내려가는 경사로를 설치하기에 남은 칸이 부족한 경우이므로 길을 지나가는 데에 실패한 경우이다.
다만, 이때도 한 칸이 지났으므로 쿨타임이 1 줄어들기 때문에, 실질적으로는 쿨타임이 2 이상인 경우를 확인해야 한다.

#!python

from sys import stdin
input = stdin.readline

# 주어진 board에서 길의 개수를 구하는 함수
def solve(board):
    ans = 0
    for line in board:
        # up_cooltime은 한 칸 올라가는 경사로를 설치하기 위해 필요한 남은 칸의 개수
        # down_cooltime은 한 칸 내려가는 경사로를 설치하기 위해 필요한 남은 칸의 개수
        # 올라가는 경사로는 앞에 l개의 칸이 필요하므로 l로, 내려가는 경사로는 처음부터 설치할 수 있으므로 0으로 초기화
        up_cooltime = l
        down_cooltime = 0
        for i in range(n - 1):
            # 한 칸 지날 때마다 쿨타임을 1씩 줄인다, 즉 필요한 칸이 하나씩 채워진다
            up_cooltime -= 1 if up_cooltime else 0
            down_cooltime -= 1 if down_cooltime else 0
            # 높이가 같으면 그냥 패스
            if line[i] == line[i+1]:
                pass
            # 한 칸 높아지는 경우 올라가는 쿨타임이 있으면 실패
            # 아니면 경사로를 놓으면 되고 쿨타임이 경사로 길이만큼 발생한다
            # 다시 말해 경사로 길이만큼 빈 칸이 있어야 다음 올라가는 경사로를 놓을 수 있다
            # 내려가는 경사로는 올라간 다음에 바로 놓아도 상관 없으므로 갱신할 필요가 없다
            elif line[i] + 1 == line[i+1]:
                if up_cooltime:
                    break
                up_cooltime = l
            # 한 칸 낮아지는 경우 내려가는 쿨타임이 있으면 실패
            # 아니면 경사로를 놓는데, 경사로는 현재 칸부터 l개의 칸에 설치되므로 l의 쿨타임이 발생한다
            # l개의 칸 동안은 높이가 높아져도, 낮아져도 안 되므로 up과 down에 둘다 l의 쿨타임이 발생한다
            # 그런데, 경사로는 겹칠 수 없으므로 올라가려면 내려가는 경사로가 끝난 뒤에도 l의 쿨타임이 추가로 발생한다
            # 즉, 올라가는 경사로는 내려가는 경사로가 끝난 뒤에도 l개의 빈 칸이 필요하다
            elif line[i] == line[i+1] + 1:
                if down_cooltime:
                    break
                down_cooltime = l
                up_cooltime = l * 2
            # 높이 차이가 2 이상인 경우 무조건 실패
            else:
                break
        # 한 번도 실패하지 않고(즉 break 없이) 반복문을 순회한 경우
        # down_cooltime이 남아있다면 내려가는 경사로를 놓을 칸이 부족한 경우이므로 실패이다
        # down_cooltime이 마지막 칸에서 1 줄어드므로 > 0이 아니라 > 1로 한 것
        # 즉, down_cooltime -=1; if down_cooltime: 과 동치이다
        else:
            if down_cooltime > 1:
                continue
            ans += 1
    return ans

n, l = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
board_trans = [[] for _ in range(n)]

# board_trans, 즉 원래 보드를 transpose한 board를 만든다
# 그냥 인덱스 바꿔서 해도 되겠지만 어차피 입력이 작으니 편하게 그냥 보드를 하나 더 만든다
for line in board:
    for i, e in enumerate(line):
        board_trans[i].append(e)

# 원래 보드의 길 개수 + transpose한 보드의 길 개수
print(solve(board) + solve(board_trans))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑