글 읽기 - 기존 질문들을 훑어보아도 예외찾기가 어렵네요~ 도와주세요!

allgoodlife 7년 전 0

1. 전제

A[n] -> n번째 계단의 score

dp[a][0] -> a번째 계단까지 오를때, 한컨 건너서 올라온 경우(2칸 전에서 뛰어올라온 경우)

dp[a][1] -> a번째 계단까지 오를때, 연속해서 올라온 경우(바로 전칸에서 온 경우)

1~2의 경우 초기화 해주었습니다.

2. 점화식

dp[n][0] = max(dp[n-2][0], dp[n-2][1]) + A[n]

dp[n][1] = dp[n-1][0] + A[n]

3. 1,2를 바탕으로 코딩을 했으며, 테스트 케이스와 질문 게시판에 있는 타 케이스들을 넣어서 확인해 봤는데 틀린 부분을 잘 못찾겠네요.

도와주시면 감사하겠습니다.

#include <iostream>
using namespace std;
int stair[301];
int dp[301][2];

int max(int a, int b) {
	if (a > b)
		return a;
	else
		return b;
}


int main(void) {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> stair[i];
	}

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

	for (int i = 3; i <= n; i++)
	{
		dp[i][0] = max(dp[i-2][0],dp[i-2][1]) + stair[i];
		dp[i][1] = dp[n-1][0] + stair[i];
	}
	cout << max(dp[n][0],dp[n][1]) << endl;

	return 0;
}

unused 7년 전 1

dp[i][1] = dp[n-1][0] + stair[i];

이거 dp[i-1][0]이어야 맞는 것 아닌가요?

allgoodlife 7년 전 0

오.. 감사합니다~ 이런실수를 하다니 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

기존 질문들을 훑어보아도 예외찾기가 어렵네요~ 도와주세요!

allgoodlife 7년 전 0

unused 7년 전 1

allgoodlife 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말