DP4 [프로그래머스] 코딩테스트 연습 > 동적계획법(Dynamic Programming) > 정수 삼각형 (C++) // c++ #include using namespace std; int solution(vector triangle) { int answer = 0; vector d(510, vector(510, 0)); // triangle 배열의 데이터를 d 배열에다가 붙여넣기 for (int i = 0; i < triangle.size(); i++) { for (int j = 0; j < triangle[i].size(); j++) d[i][j] = triangle[i][j]; } // 점화식 세운 것을 기반으로 반복문 돌리기 for (int i = 0; i < triangle.size(); i++) { for (int j = 0; j < triangle[i].size(); j++) { if (.. 2022. 4. 6. 동적 프로그래밍 (DP) 해결 방법 동적 프로그래밍 (DP) 해결 방법 Step 1 : n이 가장 작을 때부터 하나하나 그려가보면서 규칙성을 찾는다 Step 2 : 규칙성이 보이기 시작하면 일반화하고, 점화식을 구한다. Step 3 : 탑다운 or 바텀업 중 좀 더 편한 방법으로 구현 (물론 연습할 때는 둘 다 해보기) 탑다운의 필수 요구사항, 바텀업의 필수 요구사항 꼭 숙지하기 탑 다운 필수요구사항 1. 값이 한없이 작아지는 것을 방지하기 위한 탈출조건 (n이 0이거나 1 정도에서 return 하고 끊는 조건이 필요) 2. memoization (시간 초과 방지) 3. 과거의 상태값을 불러올 때는 인덱스를 이용한 배열 직접 접근보다는 재귀함수를 이용한다. Example) dp[n-1] (X) => solve(n-1) (O) 바텀 업 필수.. 2022. 2. 6. [백준] 11052번 : 카드 구매하기 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net //C++ #include #define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define pi 3.1415926535 using namespace std; typedef long long ll; int p[1001]; int d[1001]; int main() { F_I; int n; int ans; cin >> n; for (int i.. 2020. 8. 10. [백준] 2579번 : 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net #include using namespace std; int arr[301]; int dp[301]; int main() { int n; cin >> n; for (int i = 0; i > arr[i]; dp[0] = arr[0]; dp[1] = max(arr[0] + arr[1], arr[1]); dp[2] = max(arr[0] + arr[2], arr[1] + arr[2]);.. 2020. 6. 24. 이전 1 다음
