https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 이 문제는 DP 문제로 처음값과 두번째 값을 정해 준 뒤, 3번째 값부터는 dp[i-2]값과 array[i-1]값중 가장 큰 값이랑 array[i]값이랑 더한 후에, 구한 값과 dp[i-1]중 가장 큰 값을 찾으면 그 값이 해당 개수에서의 가장 큰 값이 된다. 그 후에 현재 array[i] 값에는 현재 값과 dp[i-2] 값을 더한 값으로 다시 세팅해주면 된다. package DP; import j..
https://www.acmicpc.net/problem/17953 17953번: 디저트 창호는 매일 점심마다 디저트를 먹는다. 그런데 같은 디저트라도 매일 느끼는 맛이 달라진다. 어떤 날에는 마카롱을 먹고 매우 행복함을 느끼는 반면 어떤 날에는 ‘차라리 케이크를 먹는게 나 www.acmicpc.net 전형적인 DP 문제이다. 위 그림과 같이 디저트의 개수가 10개 이하이므로 이전의 디저트 행복도의 값과 다음 행복도의 합을 비교하여 더 큰 값을 앞에다 넣어주는 방식을로 구현하였다. 같은 디저트를 섭취할 경우에는 다음 디저트의 행복도를 2로 나눈 값으로 비교하였다. package DP; import java.io.BufferedReader; import java.io.IOException; import j..
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 이 문제는 아래서부터 위로 올라오는 형태로 올라가면서 더했을 때 가장 큰 숫자를 더해주는 방식으로 계산하였다. 푸는 방법만 알면 구현하는것은 어렵지 않다. package DP; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public cla..
DP란? 한줄로 정리하면 이전 값의 결과를 저장해서 다음 결과 값을 이전 결과값의 값을 사용하여 불필요한 계산을 줄이는 것이다. 말로 설명하면 참 애매한 말인데 가장 쉽게 이해할 수 있는 것은 피보나치 수열이다. 피보나치 수열은 처음 1,1로 시작하여 그 다음 수는 그 이전의 두 개의 수의 합으로 결정되기 때문에 이것을 n까지의 입력을 받아 n순서의 피보나치 코드로 구현해보면 n = int(input()) result = [0]*n a = 0 b = 1 result[0] = a result[1] = b for i in range(2,n): result[i] = result[i-2] + result[i-1] print(result[-1]) 처음값과 두번쨰 값을 저장해 두면 3번째 부터는 자동으로 뒤의 값을..
