dynamic programming2 동적 프로그래밍 (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. [백준] 1932번 : 정수 삼각형 출처 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 www.acmicpc.net #include int numbermax(int m, int n) { int ans = m > n ? m : n; return.. 2020. 2. 25. 이전 1 다음
