1일 1커밋 !

1일 1PS 68일차!

📚 문제

골드 2 연료가 부족해

💡 풀이 과정

  • 문제를 보자마자 대부분은 DFS 를 사용해 풀었을 것이다.
  • 실제로 충분히 풀이는 가능하지만 시간 초과가 발생한다.
  • 힌트는 이분 탐색이다.
    • 정답 x 를 두고 이분탐색해 찾아나가는 것이다.

  • 결국 최대 x 는 R + C - 2 이며, x 가 주어졌을 때 충분히 도착하면 start = mid + 1, 도착하지 못하면 end = mid - 1 이다.

  • 이제 x 로 도착하느냐 못하느냐를 결정지어야한다.
    • N + 2 길이의 배열을 생성한다. 처음 출발과 피라미드 도착을 포함해 N + 2 개가 존재한다.
    • 해당 dp 배열은 각 번째 연료 보관소에 도착했을 때 남아있는 연료의 양이다.
    • 즉, 도착하지 못했다면 초기값을 그대로 가지고 있다.
  • 이제 1 ~ N + 2 까지 순서대로 체크하면서 이전에 연료 보관소에서 해당 보관소까지 도착할 수 있는 지 계산하고 도착했을 때 최대 연료량을 기록한다.
  • 이후 배열의 마지막에 도착한다면 피라미드에 도착하는 것이다.

📌포인트

  • 이분탐색
    • 실제 아이디어를 어떻게 떠올릴 수 있을까?
    • 처음에는 무조건 DFS 를 떠올릴 것 같긴하다.
    • 하지만 실제 풀면서도 4방면이 아닌 증가하는 방향으로만 가는 것에 이질감을 느꼈다.
    • 이분탐색을 위해 x 가 성공이냐 아니냐에 대해서 빠른 판단이 가능한 지도 중요하다.
    • 이건 많은 경험이 필요한 영역이지 않을까 싶다.

💻 코드

# DFS 시간초과 코드

import sys
from collections import deque

dx = [1, 0]
dy = [0, 1]

R, C = map(int, sys.stdin.readline().split())
N = int(sys.stdin.readline())

board = [[0 for _ in range(C)] for _ in range(R)]
dp = [[9999 for _ in range(C)] for _ in range(R)]
dp[0][0] = 0

for _ in range(N):
    x, y, f = map(int, sys.stdin.readline().split())
    board[x - 1][y - 1] = f

def bfs():
    queue = deque()
    queue.append((0, 0, 0, 0))

    while queue:
        x, y, f, g = queue.popleft()

        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]
            nf = f
            ng = g

            if g <= 0:
                nf += 1
            else:
                ng -= 1

            if nx >= R or ny >= C or dp[nx][ny] < nf:
                continue
            dp[nx][ny] = nf
            queue.append((nx, ny, nf, ng + board[nx][ny]))

    return dp[R - 1][C - 1]


print(bfs())



import sys

input = sys.stdin.readline

R, C = map(int, input().split())
N = int(input())

fuels = []
for _ in range(N):
    fuels.append(list(map(int, input().split())))

fuels.append([1, 1, 0])
fuels.append([R, C, 0])

# 맨해튼 거리를 기준으로 오름차순 정렬
fuels.sort(key=lambda x: x[0] + x[1])


# 맨허튼 거리 계산. i > j 가 전제 조건.
def distance(i, j):
    return (fuels[i][0] - fuels[j][0]) + (fuels[i][1] - fuels[j][1])


# x 로 피라미드에 도착할 수 있는 지 판단
def find(x):
    global R, C, N
    dp = [-1] * (N + 2)

    dp[0] = x
    fuels[0][2] = x

    # 1 ~ N + 2 순서대로 도착했을 때 가장 많은 연료가 남는 경우를 찾는다.
    # i 번째에 도착하기 위해 0 ~ i-1 번째에서 출발하는 경우의 수를 모두 검토한다.
    for i in range(1, N + 2):
        for j in range(i):
            # 오른쪽 혹은 위로만 움직여야하는 조건 체크
            if fuels[j][0] > fuels[i][0] or fuels[j][1] > fuels[i][1]:
                continue

            # 현재 가지고 있는 연료로 j 에서 i 까지 갈 수 있는 지 판단
            if dp[j] < distance(i, j):
                continue

            # dp[i] 에 도착했을 때, 연료가 가장 많이 남아있도록 max 할당
            dp[i] = max(dp[i], dp[j] - distance(i, j) + fuels[i][2])

    # dp 의 마지막 요소 (피라미드) 이 연료가 -1 이 아니라 최신화 되었다면 도착했다는 뜻.
    if dp[-1] >= 0:
        return True
    # -1 이라면 도착하지 못했다. x 보다 더 많은 연료가 필요하다.
    else:
        return False


# 처음에 충전하는 연료의 양을 기준으로 이분탐색
start = 1
end = R + C - 2

while start <= end:
    mid = (start + end) // 2

    if find(mid):
        end = mid - 1

    else:
        start = mid + 1

print(start)

업데이트:

댓글남기기

참고