본문 바로가기

728x90

DP7

[java 백준] 실버 1/ 11052번 카드 구매하기 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import java.util.Scanner; public class Main { public static int n; public static int[] arr; public static int[] dp; public st.. 2021. 8. 10.

[DP기초] 필요한 동전의 최소개수 구하기 2원,3원,5원의 동전이 있고 이 동전들을 조합해서 최소개수로 그 합이 11이 나오게 해보자. 5원x1+3원x2+2원x0 =11 -->3 5x1 + 3x0 + 2x3 =11 -->4 5x0 + 3x1 + 2x4 =11 -->5 5x0 + 3x3 + 2x1 =11 -->4 그러면 최소개수는 3이다. f(11)의 경우 11에서 2를 뺀 f(9) 11에서 3을 뺀 f(8) 11에서 5를 뺀 f(6) 으로 subproblem들을 나눌 수 있다. f(11)=Math.min(f(9),f(8),f(6))+1 이것을 일반화하면 f(n)=Math.min(f(n-2),f(n-3),f(n-5))+1 f(0)=0 f(1)은 1원짜리 동전이 없으므로 특수 케이스이기 때문에 -1 f(2)는 2원짜리 동전이 있으므로 1 f(3)은.. 2021. 8. 6.

[DP기초] 계단오르기 코드없는 프로그래밍 님의 DP강의 중 최소비용 계단오르기 강의를 참고하여 작성했습니다 https://www.youtube.com/watch?v=lhZTYwHgrDM&list=PLDV-cCQnUlIa0owhTLK-VT994Qh6XTy4v&index=3 계단이 n개까지 있을 때, n층에 올라갈 수 있는 방법은 f(n)=f(n-1)+f(n-2)이다. f(1)=1 f(2)=2 --> 한칸 씩, 한번에 올라가는 f(3)=3 등등이다. 그러면 가장 최소비용으로 계단을 올라가는 방법을 알아보자. [1,2,4,6,2] 의 5층의 계단이 있다. f(0)=0+1이다 왜냐하면 바닥에서 한번에 올라갈 수 있고, arr[0]=1(여기서 arr[0]은 0층의 값을 나타냄) 이므로 0+1=1이다. f(1)=0이다. 얘도 바닥에서 .. 2021. 8. 6.

[java 백준] 실버 2/ 11055번 가장 큰 증가 부분 수열 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 import java.util.Scanner; public class Main { pub.. 2021. 8. 5.

이전 1 2 다음

728x90

티스토리툴바