[파이썬] 백준 2253 : 점프 (골드4)

[파이썬] 백준 2253 : 점프 (골드4)

2253번: 점프

---

문제

---

풀이

 

0. 방향성 생각

• 전형적인 2차원 DP
• 같은 노드 x라도 어떤 속도로 접근했냐에 따라서 다음의 선택지가 바뀌므로 위치 x와 속도 v로 DP 테이블을 만든다
• x번째 발판에 속도 v로 도달했을 때 최솟값을 DP에 기록하자.
• N = 10000이므로 최대 속도는 약 141이다. cf) 1+2+...+k = {k*(k-1)}/2 > N인 k를 찾는다. sqrt(20000)
• 넉넉잡아서 최대 속도를 150으로 제한하고 문제를 푼다. (메모리 차이가 크게 나지 않는다)

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()
N,M = map(int,input().split())
trap = set(int(input()) for _ in range(M))

• 밟지 못하는 돌은 trap에 set으로 저장한다.

2. 함수 정의

# dp[v][x] x번째 위치에 갈 때 속도 v로 갈 경우 최솟값
dp = [[inf]*(N+1) for _ in range(150)] # 가속도가 1인 채로 유지해서 갈 경우 k(k-1)/2 > 10000인 k
dp[0][1] = 0
if 2 not in trap:
    dp[1][2] = 1

• DP 테이블 초기화.
• 처음 위치는 속력 0, 두 번째 위치가 트랩이 아닌 경우 속도 1로 접근

3. DP 테이블 업데이트 및 출력

for x in range(2,N): # x에
    for v in range(150): # 속도 v로 위치한 말이
        for nv in (v-1,v,v+1): # nv 속도로
            nx = x + nv # nx에 이동하는 경우
            if nx <= N and 1<=nv<150 and nx not in trap: # 돌다리 범위 / 1칸 이상 / 작은 돌멩이 x
                dp[nv][nx] = min(dp[nv][nx],dp[v][x]+1)
                
answer = min(dp[i][-1] for i in range(150))
print(answer if answer != inf else -1)

• nv loop를 도는 와중에 범위가 2개씩 겹쳐서 시간이 조금 더 걸렸다.
• O(3*(N**2))인데 루프문을 잘 짜면 O(N**2)까지 줄일 수 있다.

 

---

전체코드

#### 백준 2253 골드4 점프

N,M = map(int,input().split())
trap = set(int(input()) for _ in range(M))
# %%
inf = float('inf')

# dp[v][x] x번째 위치에 갈 때 속도 v로 갈 경우 최솟값
dp = [[inf]*(N+1) for _ in range(150)] # 가속도가 1인 채로 유지해서 갈 경우 k(k-1)/2 > 10000인 k
dp[0][1] = 0
if 2 not in trap:
    dp[1][2] = 1

for x in range(2,N): # x에
    for v in range(150): # 속도 v로 위치한 말이
        for nv in (v-1,v,v+1): # nv 속도로
            nx = x + nv # nx에 이동하는 경우
            if nx <= N and 1<=nv<150 and nx not in trap: # 돌다리 범위 / 1칸 이상 / 작은 돌멩이 x
                dp[nv][nx] = min(dp[nv][nx],dp[v][x]+1)
                
answer = min(dp[i][-1] for i in range(150))
print(answer if answer != inf else -1)

 

코멘트

맥시멈 속도 제한을 if문에 넣는거를 까먹어서 삽질좀 했다.

v에서 nv를 만드는 loop에서 범위가 2개씩 겹쳐서 시간이 조금 더 걸렸다.