[BOJ] 22871 징검다리 건너리 (large)
첫 번째 풀이 (시간 초과)
dp[x][y]
: x
에서 y
로 가는 의 최솟값
solve(x, y)
: dp[x][y]
를 구하는 함수. 재귀로 구현
0->4만 구하면 되는데 모든 경우를 구하다 보니 재귀가 지나치게 많아져서 시간초과인 것으로 생각된다.
두 번째 풀이 (정답)
dp[x]
: x
에서 N-1
까지 가는 의 최솟값
solve(x)
: dp[x]
를 구하는 함수. 재귀로 구현
코드
import sys
#sys.stdin = open('input.txt', 'r')
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
dp = [-1 for _ in range(N)]
def solve(start):
# 시작과 목표가 같으면 0
if start == N - 1:
dp[start] = 0
return 0
# 이미 계산한 거리라면 바로 리턴
if dp[start] != -1:
return dp[start]
# 리턴값
ret = float('inf')
# start -> i -> (N - 1)
for i in range(start + 1, N):
cost = (i - start) * (1 + abs(A[start] - A[i]))
tmp = max(cost, solve(i)) # 최대 힘(K)
ret = min(ret, tmp) # K의 최솟값
dp[start] = ret
return dp[start]
answer = solve(0)
print(answer)
Author And Source
이 문제에 관하여([BOJ] 22871 징검다리 건너리 (large)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@ahj1592/BOJ-22871-징검다리-건너리-large
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
#sys.stdin = open('input.txt', 'r')
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
dp = [-1 for _ in range(N)]
def solve(start):
# 시작과 목표가 같으면 0
if start == N - 1:
dp[start] = 0
return 0
# 이미 계산한 거리라면 바로 리턴
if dp[start] != -1:
return dp[start]
# 리턴값
ret = float('inf')
# start -> i -> (N - 1)
for i in range(start + 1, N):
cost = (i - start) * (1 + abs(A[start] - A[i]))
tmp = max(cost, solve(i)) # 최대 힘(K)
ret = min(ret, tmp) # K의 최솟값
dp[start] = ret
return dp[start]
answer = solve(0)
print(answer)
Author And Source
이 문제에 관하여([BOJ] 22871 징검다리 건너리 (large)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ahj1592/BOJ-22871-징검다리-건너리-large저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)