문제 링크

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

문제 설명

• 사다리 타기를 하는데 현재 사다리 정보가 주어짐
• 사다리를 x개 더 놓아서 i번째에서 i번째로 가도록 하려고 할 때, x의 최솟값 출력

풀이

• 새로 사다리를 놓을 수 있는 위치들을 구함
• 위치들 중 0개 선택 ~ 3개 선택하는 모든 경우를 체크 (combinations)
• i에서 i로 갈 수 있으면 break
• 3개 선택해도 갈 수 없으면 -1 출력

후기

• 어려워 보이고 시간초과 날 것 같고 그랬는데 막 풀었더니 바로 됐다
• 문제에서 놓을 수 있는 사다리의 개수를 3개로 제한해줘서 괜찮은 것 같다

코드

def possible(num):
    for combi in combinations(positions, num):
        if meet(combi):
            continue
        if i_to_i(combi):
            return True
    return False


def meet(combi):
    for i, j in combi:
        if (1 <= j-1 and board[i][j-1]) or (j+1 <= n-1 and board[i][j+1]):
            return True
    return False


def i_to_i(combi):
    result = True
    for i, j in combi:
        board[i][j] = True
    for j in range(1, n+1):
        if j != get_x(j):
            result = False
            break
    for i, j in combi:
        board[i][j] = False
    return result


def get_x(j):
    y, x = 0, j
    while True:
        y += 1
        if y > h:
            break
        if board[y][x]:
            x += 1
        elif board[y][x-1]:
            x -= 1
    return x


# init
from itertools import combinations
import sys
read = sys.stdin.readline
n, m, h = map(int, read().split())
board = [[0 for _ in range(n+1)] for _ in range(h+1)]
for _ in range(m):
    a, b = map(int, read().split())
    board[a][b] = 1
positions = []
for i in range(h+1):
    for j in range(n):
        if not board[i][j]:
            positions.append((i, j))

# start
answer = -1
for num in range(4):
    if possible(num):
        answer = num
        break
print(answer)