글 읽기 - 선배님들 도와주세요ㅜㅜ 반례좀 부탁드립니다

ckddnr0408 2년 전 0

이 문제 하나로 몇 일을 잡고 있습니다. 게시판의 반례란 반례는 다 집어 넣어본거 같은데 틀리게 나온게 없습니다.

제 로직에도 저는 문제가 없는거 같은데 이유를 모르겠습니다. 제출하면 제출하자마자 틀렸다고 나옵니다. 반례좀 찾아주세요.

코딩에 정떨어 지기 일보 직전 입니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define MAX(x, y) (((x)>(y))?(x):(y))

int dp(int* list, int n) {
	int cnt;
	int memoization[2][301] = {0, };	// memoization[0][i] -> 계단을 밟았을때 최댓값, memoization[1][i] -> 계단을 밟지 않았을때 최댓값
	int i;

	memoization[0][n] = list[n];
	memoization[0][n - 1] = list[n - 1] + memoization[0][n];
	memoization[1][n - 1] = memoization[0][n];

	cnt = 2;

	for (i = n - 2; i >= 1; i--) {
		cnt++;

		memoization[1][i] = memoization[0][i + 1];	// 계단을 건너 뛰는 경우

		// 계단을 건너 뛰지 않는경우
		if (cnt == 3) {	// 연속 세 계단을 밟기 때문에 밟고 지나는 것은 x
			memoization[0][i] = list[i] + memoization[1][i + 1];
			cnt = 1;
		}
		else {	// 밟고 지나가는 것이 가능, 윗 계단을 밟은 경우와 안 밟은 경우의 최댓값을 넣음
			if(memoization[0][i+1] > memoization[1][i+1])
				memoization[0][i] = list[i] + memoization[0][i + 1];
			else {
				memoization[0][i] = list[i] + memoization[1][i + 1];
				cnt = 1;
			}
		}
	}

	memoization[0][0] = MAX(memoization[0][1], memoization[1][1]);

	return memoization[0][0];
}

int main() {
	int n;	// 계단의 개수
	int stairs[301] = { 0, };
	int score;
	int i;

	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		scanf("%d", &stairs[i]);

	score = dp(stairs, n);

	printf("%d", score);

	return 0;
}

g072923 2년 전 4

반례드립니다

5
5 4 3 2 1

정답 12

출력 9

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

문제

문제

출처

ICPC

선배님들 도와주세요ㅜㅜ 반례좀 부탁드립니다

ckddnr0408 2년 전 0

g072923 2년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말