분류 전체보기 (157) 썸네일형 리스트형 [java] 백준/1010 다리놓기 위의 문제는 다이나믹 프로그래밍으로 풀수 있는 문제 유형이다. 다리를 직접 그려서 해보는 것이 가장 빠르게 이해가 편하다. n은 서쪽 사이트 m은 오른쪽 사이트로 볼때 n = 1 일때는 dp[1][m] = m 이다 dp[2][4] = dp[1][1]+dp[1][2]+dp[1][3]; dp[n][m] = dp[n-1][1]+dp[n-1][2] ......dp[n-1][m-2]+dp[n-1][m-1]; package practice; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringT.. [java] 백준/11052 카드구매하기 위의 문제는 다이나믹 프로그래밍의 유형중에 하나이다. n개의 카드를 구매한다고 했을때 2개짜리카드 팩을 선택하고 삿을떄의 경우 dp[n-2] +num[2] 그렇다면 dp[1]부터 시작했다고 했을때 n개의 카드를 구매한다고 했을때 x개짜리카드 팩을 선택하고 삿을떄의 경우 dp[n-x] +num[x] 단 x범위는 x [java] 백준/11053 가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열.. A[i-1] , A[i] 비교 package basic; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class LongIncrasesu { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int ans = 0; int n = new Integer(br.readLine()); int num[] = new int [n]; int dp[] = new .. [java] 백준/11727 2xn 타일링 2 dp[n] = dp[n-1]+dp[n-2]*2 dp[1] 과 dp[2]일때 값은 따로 구해야한다! dp[1] = 1; dp[2] =3 ; [java] 백준/10844 쉬운계단수 길이를 N이라 하고 L을 마지막 자리수값으로 할때 N = 1 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 9 dp[n][L] 1부터 9까지 1대입 0은 올수없으므로 제외 N= 2 L이 0일떄 dp[2][0] = dp[1][1] -> 10 n이 1이고 l이 1인값 L이 1~8 사이일때 dp[2][1] = dp[1][2] +dp[1][0] ->12 dp[1][0]은 01 이므로 dp[1][0]이 0이다.. dp[2][2] = dp[1][1] +dp[1][3] -> 21 , 23 길이가 1이고 마지막숫자가 1이나 3인값 .... L이 9일때 dp[2][9] = dp[1][8] 길이가 1이고 마지막숫자가 8 ->98 규칙... 이전자리가 0이면 그다음 자리엔 1 이전자리가 1이면 그다음자리엔 2 이나 0 이전자리가.. [java] 백준/1912 연속합 위 문제의 유형을 말하자만 다이나믹이다.. 연속된 숫자를 선택해서 가장 큰합을 구하는 문제다 10 -4 = 6 이고 3 1 5 6 까지 다 더하게 되면... 21이다 하지만 -35까지 더하면 -14가 된다.. 그뒤에도 더하게되면 -2인데 그럴빠에는 다시 12부터 시작하는게 더큰 합을 구하는 것이다. 한마디로 기존에 있던 값보다 너무 큰 마이너스 값을 더하게 될경우엔 새롭게 건너뛰에 양수때부터 시작하는게 좋다 식을 정하자면 이렇게 나온다 dp[n] = Math(dp[n-1]+num[n], num[n]) 그렇게 dp가 1에서부터 n까지의 경우를 구한뒤에 최대값을 출력하면 끝이다. [java] 백준/2156 포도주 시식 내가 포도주 시식과 계단오르기 문제를 비교해서 해본 결과 이런 문제의 접근은 마지막에서 보는것이 좋은 거같다. 다이나믹 프로그래밍을 해야하므로.. 마지막의 세부분 oox , xoo , oxo 은 무조건 이 세개중에 하나이다... oox는 dp[n] = dp[n-1] xoo는 dp[n] = dp[n-3]+wine[n]+wine[n-1] oxo는 dp[n] = dp[n-2]+wine[n] 이다. 이 세가지중에 제일 max값을 저장하는 식으로 문제를 풀면 된다. dp[0] = wine[0] dp[1] = wine[1]+wine[0] dp[2] = Max(wine[0]+wine[1], wine[1]+wine[2], wine[0]+wine[2]) 이 세가지는 미리 구해놓고 시작해야하며 n의 크기에 따른 반례를 미.. [java] 백준/1932 정수삼각형 정수삼각형에 대하여 나는 세갈래로 나누었다.. 다이나믹으로 구현하였고.. 맨 왼쪽 , 맨 오른쪽, 중간 완전왼쪽으로는 죽 더하는 구간과 완전 오른쪽으로 죽 더하는 구간 중간 구간에서 비교하는 구간.. 그런다음 마지막에서 큰 값을 받아서 출력한다. 이전 1 ··· 13 14 15 16 17 18 19 20 다음
