[Python/Baekjoon] 2253. 점프

정나린·2022년 10월 18일

💬 문제

문제 난이도: 백준 골드 4

문제 링크: https://www.acmicpc.net/problem/2253

❗️접근 방법

시작점 1번 돌에서 최소한의 횟수로 점프를 해서 N번 돌에 딱! 도착해야 한다.
현재 위치에 도달할 때의 점프 간격(step)을 기준으로 다음에 뛸 때 step-1, step, step+1 간격으로 뛸 수 있다. (단, step-1 > 0)
고려해야 하는 변수
1) 현재 위치
2) 현재 위치에 도달했을 때의 점프 간격(step)
3) 현재 위치에 도달하기까지 뛴 횟수
dp에 무엇을 저장해야 하고, 인덱스로 무엇을 두어야 할까?
- dp[돌 번호(i)][돌 번호에 도착했을 때의 점프 간격(j)] = i에 j로 착지했을 때 N번 노드에 딱! 맞게 도착하기 위해 i에서부터 뛰어야 하는 횟수 중 최소 값
-> 즉, 인덱스1: 돌번호 / 인덱스2: 점프 간격 / 값: 뛴 횟수

💢 답은 나오지만 시간초과나는 코드

# 점프
import sys
input = sys.stdin.readline
print = sys.stdout.write
sys.setrecursionlimit(10**8)

N, M = map(int, input().split(' '))
dp = [[sys.maxsize]*(int((2 * N)** 0.5) + 2) for _ in range(N+1)]
small = set()
for _ in range(M):
    small.add(int(input()))
dp[1][0] = 0 # 0번째 인덱스: 돌 번호, # 1번째 인덱스: step
answer = sys.maxsize

def solution(step, stone):
    global answer
    if stone == N:
        answer = min(answer, dp[N][step])
    for i in range(step-1, step+2):
        if i <= 0:
            continue
        new_stone = stone + i
        if (new_stone <= N) and (new_stone not in small):
            if dp[new_stone][i] > dp[stone][step]+1:
                dp[new_stone][i] = dp[stone][step] + 1
                solution(i, new_stone)

solution(0, 1)
if answer == sys.maxsize:
    print('-1')
else:
    print(f'{answer}')

✅ 정답 코드

# 점프
import sys
input = sys.stdin.readline
print = sys.stdout.write
sys.setrecursionlimit(10**8)

N, M = map(int, input().split(' '))
dp = [[0]*(int((2 * N)** 0.5) + 2) for _ in range(N+1)]

# 착지할 수 없는 돌 번호를 담아둘 집합
small = set()
for _ in range(M):
    small.add(int(input()))

# 도착점인 N번 돌에 딱! 맞게 도착했을 때, flag == True
flag = False
def dfs(step, stone):
    global flag
    if stone == N:
        flag = True
        return 0

	# 이미 인자로 주어진 step으로 stone에 방문한 이력이 있다면
    	# dp[stone][step]에 step으로 방문한 stone에서부터 도착점 N까지 가기 위한 최소 점프 횟수가 기록되어 있음
    if dp[stone][step]:
        return dp[stone][step]

	# 위의 if문의 조건에 맞지 않아 여기까지 왔다는 것은
	# step으로 stone에 처음 방문했다는 의미
    min_cost = N+2  # N+2: 의미 없는 큰 수(sys.maxsize랑 같은 의미)
    for i in range(step-1, step+2):
        if i <= 0: # step은 양수이어야 하니까
            continue
            
        # new_stone: 현재 위치 stone에서 i만큼의 간격으로 뛰었을 때 도착할 돌의 번호
        new_stone = stone + i 
        
        # 가게 될 곳이 범위를 벗어나지 않아야 하고, 착지하지 못할 곳이면 안되기 때문에
        if (new_stone <= N) and (new_stone not in small):
        
        	# 위의 조건을 만족한 new_stone에서 도착점인 N까지 얼마나 가면 되는지를 알기 위해 dfs를 재귀적으로 호출하고
            # 현재 위치인 stone에서 new_stone으로 1번 뛰었으니 +1
            tmp = dfs(i, new_stone) + 1
            
            if tmp < min_cost:
                min_cost = tmp
    dp[stone][step] = min_cost
    return dp[stone][step]

answer = solution(0, 1)
if flag:
    print(f'{answer}')
else:
	# 시작점 1번 돌에서 도착점 N번 돌로 가는 방법이 없을 경우
    print('-1')

(참고한 코드: https://velog.io/@tpclsrn7942/%EB%B0%B1%EC%A4%80-2253%EB%B2%88-%EC%A0%90%ED%94%84)

✍️ 시간 줄이는 꿀팁!

dp[stone][step] = min(dp[stone][step], dfs(i, new_stone)+1)

min_cost = sys.maxsize
tmp = dfs(i, new_stone)+1
if tmp < min_cost: 
	tmp = min_cost
dp[stone][step] = min_cost

1번 방식보다 2번 방식이 시간이 적게 걸린다.
2차원 배열을 매번 load하고 값을 write하는 것 하는 것보다(1번 방식)
min_cost와 tmp 변수를 새로 만들고 최종 min_cost을 write할 때만 2차원 배열을 load하고 write하면 부담이 줄기 때문인 것 같다.