DP

Algorithem/백준 PS with code

백준 #1446 - [S1] 지름길 : DP

(python3) 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net DP로 해결하기 n지점 이하의 dp 배열이 최단으로 저장되어있다는 가정하에, dp[n] = min(dp[n], dp[n-1]+1) 입니다. 바로 앞 지점에서 1만큼 더 이동하거나 이미 지름길로 더 짧게 도달하거나 둘 중 하나입니다. 그리고 지름길 시작점이 n 이라면 끝점의 dp 값을 변경해주어야 합니다. dp[끝점] = min(dp[끝점], dp[시작점]+지름길 길이) 앞서서 말한 가정을 성립시키기 위해서는 지름길들이 시작점 기준..

Algorithem/백준 PS with code

백준 #15989 - [S1] 1,2,3 더하기 4 : DP

(python3) 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 수학으로 해결하기 1,2,3으로 조합해서 수를 만드는 방법은, 3을 먼저 넣고, 남은 값을 2로 만들고, 그리고 남은 값은 1을 채우는 것과 같다. 코드 import sys def solution(input) : N = int(input().strip()) for _ in range(N) : S = 0 n = int(input().strip()) for i in range(n//3 ..

jamong5
'DP' 태그의 글 목록
상단으로

티스토리툴바