본문 바로가기

알고리즘구현능력/문제해결능력

 (78)
[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 정수삼각형 정수삼각형에 대하여 나는 세갈래로 나누었다.. 다이나믹으로 구현하였고.. 맨 왼쪽 , 맨 오른쪽, 중간 완전왼쪽으로는 죽 더하는 구간과 완전 오른쪽으로 죽 더하는 구간 중간 구간에서 비교하는 구간.. 그런다음 마지막에서 큰 값을 받아서 출력한다.
[java] 백준/2193 이친수 이친수 1 1 -> 1개 2 10 -> 1개 3 101 100 -> 2개 4 1010 1001 1000 -> 3개 5 10101 10100 10010 10001 10000 -> 5개 6 101010 101001 101001 100101 100100 100010 100001 100000 -> 8개 피보나치수열이랑 동일하게 올라간다 d[n] = d[n-1]+d[n-2]
[java] 백준/11726 2xn타일링 위 문제는 다이나믹 프로그래밍으로 풀 수 있다. d[n] = d[n-1] + d[n-2]
[java] 백준/1149 RGB거리 으.. 필자는 이해자체를 접근을 잘못해서 집의 갯수가 3개인데 3X3으로 생각을 해버리는 불상사.... 뭐 암튼 첫번째 줄엔 첫번째 집의 R,G,B 값이고 두번째 집 R,G,B 세번째 집 R,G,B 값이다... 이것도 결국 다이나믹 프로그래밍으로 풀면 된다. dp[0][0] = 26 =arr[0][0] , dp[0][1] = 40 = arr[0][1] , dp[0][2] = 83 =arr[0][2] dp[1][0] = arr[1][0](49) + Min(dp[0][1],dp[0][2]) , dp[1][1] = arr[1][1](60) +Min(dp[0][0],dp[0][2]) , dp[1][2] = arr[1][2](57) + Min(dp[0][1],dp[0][0]) dp[2][0] = arr[2][0]..
[java] 백준/1003 피보나치 함수 피보나치함수 dp[0]은 0횟수 한번출력 dp[1]은 1횟수 한번출력 dp[2]는 0횟수한번 1횟수한번 3은 위의 dp[2] , dp[1] 경우 ....40보다 작거나 같은 자연수 또는 0이라고 했으니.... 40까지 다구하고 출력만 따로 시키는 식으로 난 작업했다.

티스토리툴바