Algorithm_BOJ(백준)/동적프로그래밍(DP) (65) 썸네일형 리스트형 [백준 11726 c++ VO] 2×n 타일링 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; // [백준 11726 c++ VO] 2×n 타일링 // 문제: 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수 구하기 // 접근: n=1부터 차례로 방법의 수들 구해보기 -> 규칙(전화식 찾기) // 접근2 : dp라 생각하고 탑다운 방식으로 n번째에 더해지는 경우들을 생각 -> //n번째에는 n-1번.. [백준 1463 c++ VO] 1로 만들기 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 1463 c++ VO] 1로 만들기 // 문제: -1./3,/2 3가지 계산을 통해 1로 만들 때 최소 연산 횟수를 구하라 // 접근: 완전 -> 시간초과 예상, 그리디 -> 최소 횟수 아닌 경우 있음 틀림 // 접근2: 3가지 조건 세분화, 중복 -> dp -> n부터 탑다운 점화식으로 생각 -> 바텀.. [백준 1149 c++ VO] 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 using namespace std; // [백준 1149 c++ VO] RGB거리 // 문제: 각 집마다 서로다른 규칙을 따른 색의 비용의 최소값을 구하는 문제 // 접근: 탑다운 dp -> n번째 집이 r일때 n-1집은g,b중하나 g일때 n-1집은 r,b중 하나, b일때 n-1집은 r,g중 하나 // 점화식 : dp[j][1] = min(dp[.. [백준 15988 c++ O] 1, 2, 3 더하기 3 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; // [백준 15988 c++ O] 1, 2, 3 더하기 3 // 문제: 정수를 1,2,3의 합으로 나타내는 방법의 수를 출력 // 접근: 1,2,3 경우를 나눔 -> dp -> 탑다운 방식: 정수 i 가되는 경우 // 1.i-1 에서 1 더한 것 // 2. i-2에서 2 더한 것 // 3. i-3 에서 3 더한것 3가지 // 점화식 :.. [백준 1699 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; // [백준 1699 c++ O] 제곱수의 합 // 문제: 자연수 N을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수 구하기 // 접근1: 그리디: 큰 수부터 제곱하면서 더해서 최소항의 개수 구하기 -> 시도는 안해봄 // 접근2 : 탑다운 dp: // n이 되기위한 합의 경우는 // 1. n = (n-1^2)+1^2 , (n-2^2)+2^2.. [백준 1912 c++ V] 연속합 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 56 57 58 59 60 61 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; // [백준 1912 c++ V] 연속합 // 문제: 최대 연속된 부분수열의 합의 최댓값 구하기 // 접근1: 최대 부분수열의 합의 최댓값 알고리즘 적용 // 원소를 계속해서 더해간다 // 더한 값이 최댓값이면 최댓값 갱신 // 더함값이 음수면 0으로 초기화.. [백준 11053 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; // [백준 11053 c++ VO] 가장 긴 증가하는 부분 수열 // 문제: LIS 가장 긴 증가하는 부분수열(오름차순의 부분수열)의 길이를 구하는 문제 // 접근1: 브루트포스로 큰 수 나올 때마다 카운트해서 최대값 찾으려 생각-> 시간초과 예상으로 안함 // 점근2: dp를 이용해 각 자리마다 나오는 증가하는 부분수열의 최대값 저장 // 풀이.. [백준 2193 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; // [백준 2193 c++ VO] 이친수 // 문제: n 자리 이친수의 개수 구하기 // 접근1: dp결과값으로 규칙 찾기 -> dp[n] = dp[n-1]+dp[n-2] => 이것도 정답 // 접근2: 2차원 dp : 0으로 끝나는 경우, 1로 끝난는 경우 => 정석 dp // 풀이: // 점화식 dp.. 이전 1 ··· 3 4 5 6 7 8 9 다음