1. 과제
백준 동적프로그래밍 2579번 계단 오르기 문제
2. 참고한 사항 / 중요 사항
1차원 동적 배열 생성하기
//크기가 5인 일차원 배열 동적할당
int* arr = new int[5];
// 입력받은 n 크기대로 일차원 배열 동적할당
int n;
scanf("%d\n", &n);
int* stairs = new int[n]; c에서 배열 크기를 마음대로 지정하고 싶을 때에는 동적배열 할당으로!
2차원 동적 배열 생성하기
(문제 풀이에서 쓰지는 않았지만, 처음에 2차원 배열로 만들려고 했어서 찾아봤던거라 추가합니다)
int** arr = new int*[row]; //선언하고자 하는 이차원 배열의 행의 수 만큼 동적 할당
for(int i = 0; i < row; i++) //각각의 인덱스에 선언하고자 하는 배열의 크기만큼을 가르키게 함.
arr[i] = new int[col];배열 할당 해제하기
// 1차원 배열
delete[] arr;
// 2차원 배열
for(int i=0; i<3; i++)
delete[] arr[i];
delete[] arr;출처 : https://ya-ya.tistory.com/101
문제 풀이 원리
맨 처음 계단부터, 마지막 계단까지 차례로 올라가면서 이 계단까지 올 때의 합의 최댓값을 더하는 식으로 진행한다.
이 계단까지의 최댓값 합을 담는 dp 배열을 따로 생성하면서 진행했다.
1) 1번째 계단까지의 합의 최댓값
1번째 계단의 값이 곧 최댓값!
2) 2번째 계단까지의 합의 최댓값
1번째 계단 값 + 2번째 계단 값
3) 3번째 계단까지의 합의 최댓값
- 1번째 계단 값 + 3번째 계단 값
- 2번째 계단 값 + 3번째 계단 값
중 더 큰 값!
4) 4번째 계단까지의 합의 최댓값
- 1번 값 + 2번 값 + 4번 값
- 이 값은 즉, 2번까지의 합 최댓값(dp[2]) + 4번 값
- 1번 값 + 3번 값 + 4번 값
- 이 값은 즉, 1번까지의 합 최댓값(dp[1]) + 3번 값 + 4번 값
중 더 큰 값!
+) 2번째 '1번 값 + 3번 값 + 4번 값'에서 (1번값 + 3번값) != dp[3]인 것에 주의해야 한다! 꼭 같지 않음! 따라서 dp[1] + 3번 값 + 4번 값으로 생각해야 한다.
이를 일반화하면 4이상의 n번째 계단에 대해서는,
n) n번째 계단까지의 합의 최댓값
- n-2번째까지의 합 최댓값(dp[n-2]) + n번 값
이 값은 즉 - n-3번째까지의 합 최댓값(dp[n-3]) + n-1번 값 + n번 값
중 더 큰 값!
으로 구할 수 있다.
이 점화식을 잘 이용하면 풀 수 있다.
나는 n번째 점화식을 만드는 걸 실패해서.. 결국 다른 분의 해설을 보면서 이해하면서 풀었다.
출처 : https://yabmoons.tistory.com/510
3. 전체 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int* dp;
int* stairs;
int max_count(int n) {
dp[0] = stairs[0];
if (n > 1)
dp[1] = stairs[1] + stairs[0];
if (n > 2) {
dp[2] = (stairs[0] < stairs[1]) ? stairs[1] + stairs[2] : stairs[0] + stairs[2];
}
if (n > 3) {
for (int i = 3; i < n; i++) {
int a = dp[i - 2] + stairs[i];
int b = dp[i - 3] + stairs[i - 1] + stairs[i];
if (a > b)
dp[i] = a;
else
dp[i] = b;
}
}
return dp[n-1];
}
int main() {
int n;
scanf("%d\n", &n);
stairs = new int[n];
for (int i = 0; i < n; i++) {
scanf("%d\n", &stairs[i]);
}
dp = new int[n];
printf("%d", max_count(n));
delete[] dp;
delete[] stairs;
}+) 그런데 이 코드는 비주얼 스튜디오에서는 결과가 출력이 안 되는데 백준에서 채점을 해보면 정상적으로 맞았습니다가 뜬다... 원인은 잘 모르겠지만.. 일단 맞았습니다라고 뜬다..!
4. 제출 화면
