글 읽기 - 반례나 알고리즘의 허점을 지적해 주실 수 있을까요

zeya9643 4년 전 0

dp[0]은 이전계단을 밟고 이번계단도 밟았을때

dp[1]은 이전 계단을 밟지 않고 이번 계단을 밟았을때

dp[2]는 이전 계단을 밟고 이번 계단을 밟았을때

이 3가지로 나누어 마지막 계단까지 계산한 후 계단을 밟는 경우인 dp[0][n]와 dp[1][n] 둘중 최댓값을 계산하는 방식으로 해를 구했습니다

반례나 알고리즘의 허점을 알수 있을까요

#include <stdio.h>
#define SIZE 301

int arr[SIZE] = { 0, };
int dp[3][SIZE] = { 0, };

int Max(int f, int l)
{
	return (f > l) ? f : l;
}

int main()
{
	int n = 0;
	scanf("%d", &n);

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

	if (n > 1)
	{
		for (int i = 2; i < n + 1; i++)
		{
			dp[0][i] = arr[i] + dp[1][i - 1];
			dp[1][i] = arr[i] + dp[2][i - 1];
			dp[2][i] = Max(dp[0][i - 1], dp[1][i - 1]);
		}
	}

	printf("%d", Max(dp[0][n], dp[1][n]));
	return 0;
}

hxgn0221 4년 전 0

dp[2][i]는 i번째 계단을 밟지 않는 경우인 것 같네요

dp[0][i]를 갱신할 때 dp[0][i-1]도 비교해 줘야 할 것 같고요.

zeya9643 4년 전 0

아 밟지 않았을때라고 서야 하는걸 잘못 썻습니다

zeya9643 4년 전 0

dp [0][i]를 갱신할 때 세 칸을 연속으로 밟을 수 없으므로 dp[0][i-1]은 고려하지 않아도 되는거 아닌가요?

hxgn0221 4년 전 1

dp[0][i - 1]은 비교하지 않아야 하네요 실수...

다시 읽어보니 초기화 단계가 문제일 것 같습니다. 우선 dp[0][2]가 의도한 대로 갱신이 안 될 것 같아요. 첫 번째, 두 번째 계단의 점수를 다 더한 값이 들어가야 하는데 두 번째 계단 값만 들어온 셈이니... 그리고 dp[2][1]같은 경우는 1번 계단을 안 밟았는데 1번 계단이 들어가 있는 것 같아요.

아마도 dp[2][1] = arr[1];을 dp[1][1] = arr[1];으로 바꾸면 맞지 않을까 싶습니다.

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

문제

문제

출처

ICPC

반례나 알고리즘의 허점을 지적해 주실 수 있을까요

zeya9643 4년 전 0

hxgn0221 4년 전 0

zeya9643 4년 전 0

zeya9643 4년 전 0

hxgn0221 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말