Algorithm_BOJ(백준)/동적프로그래밍(DP) (65) 썸네일형 리스트형 [백준 1932 c++ VO] 정수 삼각형 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 51 52 53 54 55 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 1932 c++ VO] 정수 삼각형 // 문제: 정수 삼각형의 각 층에서 하나를 선택해 더할 때 최댓값 구하기, 선택한 수의 왼쪽 아래와 오른쪽 아래의 수만 선택가능 // 접근1: 최댓값(완전탐색,그리디,dp) -> 탑다운 dp로.. [백준 2156 c++ VV] 포도주 시식 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 2156 c++ VV] 포도주 시식 // 문제: 연속 3개를 마시지 않으면서 n개의 포도주를 마셔서 포도주 합의 최댓값 구하기 // 접근1: dp로 점화식 구하고 그때그때의 최댓값 저장 // 풀이: 포도주 입력 // n번째 포도주합의 최댓값 // dp 점화식 // 1. n번째 .. [백준 11057 c++ O] 오르막 수 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 51 52 53 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 11057 c++ O] 오르막 수 // 문제: 인접한 수가 같거나 증가하는 수로 구성된 수를 오르막 수라고 한다. n자리의 오르막 수의 갯수 구하기 // 접근: 갯수 구하기(완전탐색/dp) -> 탑다운 dp //-> n번째 자리가0 이면 n.. [백준 1309 c++ O] 동물원 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 1309 c++ O] 동물원 // 문제: 2*N 배열에 가로로도 세로로도 붙어있지 않게 사자를 배치하는 경우의 수, 사자가 없는 경우도 포함 // 접근: 경우의수 구하기-> 왼전,dp -> 탑다운-> n번째 행의 우리에 사자를 배치하는 경우 // dp[n][0]:n번째 행에 사자가 없는 경우, dp[n][1].. [백준 1149 c++ VOO] RGB거리 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 1149 c++ VOO] RGB거리 // 문제: 각 집마다 서로다른 규칙을 따른 색의 비용의 최소값을 구하는 문제 // 접근: 탑다운 dp -> n번째 집이 r일때 n-1집은g,b중하나 g일때 n-1집은 r,b중 하나, b일때 n-1집은 r,g중 하나 // 점화식 :.. [백준 2225 c++ X] 합분해 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 2225 c++ X] 합분해 // 문제: 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하라 // 접근 : 탑다운 dp: // n이 되기위한 합의 경우는 // dp[k][n]= k개를 이용해 합이n이 되는 경우의 수 // dp[k][n] = sum(dp[k-1][0],dp[k-1].. [백준 1699 c++ OO] 제곱수의 합 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 1699 c++ OO] 제곱수의 합 // 문제: 자연수 N을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수 구하기 // 접근1: 그리디: 큰 수부터 제곱하면서 더해서 최소항의 개수 구하기 -> 시도는 안해봄 // 접근2 : 탑다운 dp: // n이 되기위한 합의 경우는 // 1. n = (n-1^2)+1^2 .. [백준 1912 c++ VO] 연속합 //풀이 2: dp로 푼 것 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 51 52 53 54 55 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 1912 c++ VO] 연속합 // 문제: 최대 연속된 부분수열의 합의 최댓값 구하기 // 접근1: 최대 부분수열의 합의 최댓값 알고리즘 적용 // 원소를 계속해서 더해간다 // 더한 값이 최댓값이면 .. 이전 1 2 3 4 5 6 7 ··· 9 다음