-
백준 알고리즘, 2579 문제Algorithms/ACM_ICPC 2018. 8. 8. 18:25
풀이
3. 마지막 도착 계단은 반드시 밟아야 한다.
이 규칙이 가장 중요하다.
... 15 25 10 20
or
... 25 10 20
이 두가지 중 하나는 무조건 선택이 될 것이다.
즉, 다음과 같이 요약될 수 있다.
1. 마지막 직전을 선택한 경우
2. 마지막 -2 번째를 선택한 경우
결과적으로 이 두값의 크기를 비교하여 큰 값에 마지막 숫자를 더해주면 된다.
점화식은
DP[N] = max( DP[N-3] + arr[N - 1] , DP[N - 2] ) + arr[N]
이 된다.
코드
/*** @site: https://www.acmicpc.net/problem/2579* @github: https://github.com/7772* @auth: Landon Park* @date: 2018. 08. 08*/#include <iostream>using namespace std;int main() {int DP[301];int arr[301];int N, i;cin >> N;for (i = 1; i <= N; i++) cin >> arr[i];DP[0] = arr[0] = 0;DP[1] = arr[1];DP[2] = arr[1] + arr[2];for (i = 3; i <= N; i++) {DP[i] = max(DP[i - 3] + arr[i - 1], DP[i - 2]) + arr[i];}cout << DP[N] << endl;return 0;}반응형'Algorithms > ACM_ICPC' 카테고리의 다른 글
백준 알고리즘, 9461 문제 (0) 2018.08.14 백준 알고리즘, 1699 문제 (0) 2018.08.09 백준 알고리즘, 1912 문제 (0) 2018.08.08 백준 알고리즘, 11054 문제 (0) 2018.08.03 백준 알고리즘, 11722 문제 (0) 2018.08.03