본문 바로가기
728x90
반응형

알고리즘/DP37

[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.
[java 백준] 실버 2/1912번 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,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 38 39 40 41 42 import java.util.Scanner; public class Main { public static int n; public static int[] arr; public static int[] .. 2021. 8. 5.
[java 백준] 실버 3/ 2579번 계단오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 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 import java.util.Scanner; public class Main { public static int n; public static int[] arr; public static int[] dp; public static void ma.. 2021. 8. 5.
728x90
반응형