백준 2579 계단 오르기

진짜 이거 첨에 문제를 잘못읽어서

세번 연속으로 밟을 수 없다

를

세번 연속으로 한칸 씩 뛸 수 없다

라고 생각해서

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> stair;
vector<int> memo_canSingle;
vector<int> memo_cannotSingle;

int solve(int nowStair, int prev) {
	bool canSingleJump = true;
	if (abs(nowStair - prev) == 1 ) {
		canSingleJump = false;
	}

	if (nowStair == 0) {
		return memo_canSingle[0];
	}
	if (nowStair == 1) {
		if (canSingleJump) return memo_canSingle[1];
		else return memo_cannotSingle[1];
	}
	if (memo_canSingle[nowStair] > 0) {
		if (canSingleJump) return memo_canSingle[nowStair];
		else return memo_cannotSingle[nowStair];
	}

	int prev_max_score;
	int result;

	if (canSingleJump) {
		prev_max_score = max(solve(nowStair - 1, nowStair), solve(nowStair - 2, nowStair));
		result = stair[nowStair] + prev_max_score;
		memo_canSingle[nowStair] = result;
	}
	else {
		result = stair[nowStair] + solve(nowStair - 2, nowStair);
		memo_cannotSingle[nowStair] = result;
	}

	return result;


}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		memo_canSingle.push_back(0);
		memo_cannotSingle.push_back(0);
	}

	for (int i = 0; i < n; i++) {
		int score;
		cin >> score;
		stair.push_back(score);
	}

	memo_canSingle[0] = memo_cannotSingle[0] = stair[0];

	memo_canSingle[1] = stair[1] + stair[0];
	memo_cannotSingle[1] = stair[1];

	cout << solve(n-1, 1000) << endl;

}

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

이렇게 짰다

븅신ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

근데 틀린것도 아니고 메모리 초과가 뜸 ㅋㅋㅋㅋ

문제를 다시 읽으니 내가 잘못 이해했다고 그제서야 발견

그래서 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> stair;
vector<int> memo;

int solve(int nowStair) {

	if (nowStair == 0) {
		return memo[0];
	}
	if (nowStair == 1) {
		return memo[1];
	}
	if (nowStair == 2) {
		return memo[2];
	}

	int case_1 = solve(nowStair - 3) + stair[nowStair - 1] + stair[nowStair];
	int case_2 = solve(nowStair - 2) + stair[nowStair];

	memo[nowStair] = max(case_1, case_2);

	return memo[nowStair];


}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		memo.push_back(0);
	}

	for (int i = 0; i < n; i++) {
		int score;
		cin >> score;
		stair.push_back(score);
	}

	memo[0] = stair[0];
	memo[1] = stair[1] + stair[0];
	memo[2] = stair[2] + stair[0];

	cout << solve(n-1) << endl;

}

이렇게 고쳤더니

이번엔 시간 초과가 뜬다

벡터의 문제일까... 싶어서 배열로 바꾸었다.

이 문제 이후로 배열을 자주 쓴거 같다 ㅎ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int stair[301];
int memo[301];

int solve(int nowStair) {

	if (nowStair == 0) {
		return memo[0];
	}
	if (nowStair == 1) {
		return memo[1];
	}
	if (nowStair == 2) {
		return memo[2];
	}
	if (memo[nowStair] > 0) {
		return memo[nowStair];
	}

	int case_1 = solve(nowStair - 3) + stair[nowStair - 1] + stair[nowStair];
	int case_2 = solve(nowStair - 2) + stair[nowStair];

	memo[nowStair] = max(case_1, case_2);

	return memo[nowStair];


}

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		stair[i] = tmp;
	}

	memo[0] = stair[0];
	memo[1] = stair[1] + stair[0];
	memo[2] = stair[2] + stair[0];

	cout << solve(n-1) << endl;

}

이번엔 틀렸댄다 ㅋㅋ

잘 생각해보니 초기값의 문제였던거 같더라

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int stair[301];
int memo[301];

int solve(int nowStair) {

	if (nowStair == 0) {
		return memo[0];
	}
	if (nowStair == 1) {
		return memo[1];
	}
	if (nowStair == 2) {
		return memo[2];
	}
	if (memo[nowStair] > 0) {
		return memo[nowStair];
	}

	int case_1 = solve(nowStair - 3) + stair[nowStair - 1] + stair[nowStair];
	int case_2 = solve(nowStair - 2) + stair[nowStair];

	memo[nowStair] = max(case_1, case_2);

	return memo[nowStair];


}

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		stair[i] = tmp;
	}

	memo[0] = stair[0];
	memo[1] = stair[1] + stair[0];
	memo[2] = max(stair[2] + stair[0], stair[2] + stair[1]);

	cout << solve(n-1) << endl;

}

다행히 맞았다.

점화식은

DP(n) = max( DP(n-3) + stair[n-1] + stair[n] , DP(n-2) + stair[n])

stair[n]은 'n번째 계단의 점수' 이고

memo[n]은 'n번째 계단 까지 오를 때의 최고 점수' 이다.