글 읽기 - 9%에서 틀리는것 보니 , 접근 자체가 틀린것 같은데...

dlaqudanr 6년 전 0

접근 자체가 틀린것 같은데 , 전혀 감이 안오네요...

제가 푼 방식은 이렇습니다.

가장 뒤에서 부터 진행.

크게 두가지 경우로 봄.

1. 3개연속이 되는경우와 그렇지 않은경우

1-1. 3개 연속이 되는경우에는

바로 이전까지의 값(dp[i+1])과 전전값과 현재 계단값 더한 값(dp[i+2] + stair[i])
를 비교.

비교하여 큰 값을 기준으로 dp를 설정. 만약 dp[i+2]+stair 가 더 크다면 , 가운데놈의 방문 표시를 지운다.

1-1-1 (예외 처리)

둘의 값이 같을 경우 dp[i+1]의 값을 사용한다. continue 처리를 해주었다.

1-2. 3개 연속이 아니라면 단순하게 dp[i+1] + stair[i]를 해준다.

어느부분이 틀린건가요???

또한 올바른 접근 방법은 어떻게 해야하는 걸까요?

/*2579 계단오르기*/

#include<iostream>
#include<vector>
#include<stdio.h>
#include<algorithm>
using namespace std;


/*
가장 뒤에서 부터 진행.

크게 두가지 경우로 봄. 

1. 3개연속이 되는경우와 그렇지 않은경우

1-1. 3개 연속이 되는경우에는 

바로 이전까지의 값(dp[i+1])과 전전값과 현재 계단값 더한 값(dp[i+2] + stair[i])
를 비교.

비교하여 큰 값을 기준으로 dp를 설정. 만약 dp[i+2]+stair 가 더 크다면 , 가운데놈의 방문 표시를 지운다.

1-1-1 (예외 처리)

둘의 값이 같을 경우 dp[i+1]의 값을 사용한다. continue 처리를 해주었다.


1-2. 3개 연속이 아니라면 단순하게 dp[i+1] + stair[i]를 해준다.




*/
int main()
{

	int n;
	scanf("%d", &n);

	int stair[301];
	int dp[301];


	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &stair[i]);
	}


	fill(dp, dp + n+1,0);
	

	
	int check[301] = {0,};
	
	check[n] = 1;
	dp[n] = stair[n];

	for (int i = n-1; i >= 1; i--)
	{
		if (check[i + 1] == 0 || check[i + 2] == 0)
		{
		
			dp[i] = dp[i + 1] + stair[i];
			check[i] = 1;
		
		}
		else if (check[i + 1] == 1 && check[i + 2] == 1)
		{
		dp[i] = max(dp[i + 1], dp[i + 2] + stair[i]);

			
			if (dp[i+1]  == dp[i + 2] + stair[i])
			{
				continue;
			}

			if (dp[i] == dp[i + 2] + stair[i])
			{
					check[i + 1] = 0;
					check[i] = 1;
			}

		}
		
		
	}

	for (int i = 0; i <= n; i++)
	{

		cout << "dp[" << i << "] :" << dp[i] << endl;

	}

	for (int i = 0; i <= n; i++)
	{
	 cout<<i<<": "<< check[i] << endl;
	}
	

	cout << dp[1] << endl;



	return 0;

}

/*if (check[i - 1] == 0 || check[i - 2] == 0)
{
dp[i] = max(dp[i - 1] + stair[i], dp[i-2] + stair[i]);
check[i] = 1;
}
else if (check[i - 1] == 1 && check[i - 1] == 1)
{
dp[i] = max(dp[i - 1], dp[i - 2] + stair[i]);

if (dp[i] == dp[i - 2] + stair[i])
{
check[i - 1] = 0;

}
check[i] = 1;

}
*/

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

문제

문제

출처

ICPC

9%에서 틀리는것 보니 , 접근 자체가 틀린것 같은데...

dlaqudanr 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말