다이나믹프로그래밍5 백준[자바 java] 1446번 : 지름길 https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 문제설명 D킬로미터를 가야하는 세진이가 운전해야하는 거리의 최솟값을 구하는 문제이다. 풀이설명 다이나믹 프로그래밍을 사용하여 문제를 푼다. 지름길의 갯수만큼 배열을 만들어 거기에 지름길들을 입력받는다(arr) dp배열을 D만큼 만들고 배열에 각각의 수를 넣어준다(지름길이 없을 때의 운전해야하는 거리) dp에는 각각의 거리에 도달할 때 운전해야 하는 최솟값을 넣어준다. 우선 현재 위치보다.. 2023. 7. 11. 백준 [자바 java] 1495번 : 기타리스트 분명 처음 봤을 때에는 dp라고 생각했지만 막상 어떻게 풀어야 할지 생각이 나지 않아서 스택 두 개로 주고받고 하는 형식으로 풀었었다. 하지만 가차 없이 메모리 초과가 났다. 예전에 한번 풀어봤던 것 같아서 이제까지 풀었던 dp문제를 다시 쭉 봤다. 그 중 안녕이라는 문제와 제일 비슷했다. dp는 최댓값을 저장하고 나머지를 버린다라는 고정관념이 있었는데 이 dp는 한계 수가 있으면 그만큼 수열을 만들어주고 해당하는지 아닌지 표시하는 방식이다. import java.util.*; import java.io.*; class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader.. 2022. 8. 14. 백준 [자바 java] 11052번 : 카드 구매하기 이 문제는 카드 팩 별로 가격이 매겨진 카드들을 개수에 맞게 딱 사는 경우 중 가장 높은 가격을 구하는 문제이다. 처음에는 가성비가 가장 낮은 카드를 맞춰서 사는 방법을 생각했지만 너무 예외가 많았다. 그래서 dp에 1부터 차례로 값을 넣기로 했다. 예를 들어 dp [2]의 경우는 (2), (1,1)의 경우 중 더 비싼 것, dp [5]의 경우는 (1,4), (2,3), (5) 중 가장 비싼 것을 넣게 하였다. 이렇게 하면 세 묶음을 사는 경우를 굳이 고려하지 않아도 되기 때문이다. import java.io.*; import java.util.*; class Main { public static void main(String[] arg) throws IOException { BufferedReader .. 2022. 8. 1. 백준 [자바 java] 백준 2156 : 포도주시식 이 문제는 딱봐도(?) 다이나믹프로그래밍 문제이다. 조금 주의할 점이 있다면 연속으로 세 잔 이상 마실수 없다는 것! import java.io.*; import java.util.*; class Main { public static void main(String[] arg) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader (System.in)); int n = Integer.parseInt(br.readLine()); int arr[] = new int[n+1]; int[] dp1 = new int[n+1]; int[] dp2 = new int[n+1]; int i; for(i = 1;i 2022. 7. 31. 백준 [자바 java] 백준 10844 : 쉬운 계단 수 처음 이 문제를 봤을 때는 무슨 말인지 이해가 잘 되지 않아서 여러번 읽어봤다. 한마디로 n자리수들 중에서 인접한 수의 차이가 모두 1인 수들의 갯수를 구하라는 문제이다. 예를 들어 n이 2일 때 10,12,21,23,32,34...이런 수들이 있고 이들의 개수를 출력해야 하므로 출력 값은 17이다. 처음에는 수학적 공식(?)이 dp보다 훨씬 간편할 것이라고 생각했지만 그건 나의 착각이었다. 앞에는 쫌 잘 돌아갔지만 25까지만 돌아가고 뒤에는 거의 안 돌아갔다. 당연히 시간 초과가 났고 이런저런 약간의 조치를 취했지만 해결되지는 않았다ㅜ 결국 다 지우고 dp로 해결해보았다. 2차원 배열을 만든 후 세로축은 0부터 9 그리고 가로 축은 자릿수를 의미한다. 일의 자릿 수에서 끝이니까 dp[i][1]은 다 1.. 2022. 7. 31. 이전 1 다음
