글 읽기 - C++ 왜 틀린 로직일까요..

iamthejiheee 4년 전 0

path는 그냥 몇칸을 밟는지 확인하기 위해서 설정한 벡터입니다.

연속된 3개의 계단을 밟지 않도록만 하면 되는게 아닌지..

연속된 두 개의 계단은 밟아도 되는 것이라면

1 1 2 1 1 이런 식으로 밟아도 되지 않나요?

#include <bits/stdc++.h>

using namespace std;

vector<int> stairs;
vector<int> path;
int n;
int maxx = 0;

void dfs(int step, int sum, int index) {
	if (step > n) return;
	if (step == n) {
		sum = sum + stairs[step];
		if (maxx < sum) maxx = sum;
	}
	else {
		// 연속된 세 개의 계단을 밟는지 확인
		if (index >= 2 && path[index - 1] == 1 && path[index - 2] == 1) {
			path[index] = 2;
			dfs(step + 2, sum + stairs[step], index + 1);
		}
		else {
			path[index] = 1;
			dfs(step + 1, sum + stairs[step], index + 1);
			path[index] = 2;
			dfs(step + 2, sum + stairs[step], index + 1);
		}
		path[index] = 0;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n;

	stairs = vector<int>(n + 1, 0);
	path = vector<int>(n + 1, 0);
	int i, j;

	for (i = 1; i <= n; i++) {
		cin >> stairs[i];
	}

	dfs(0, 0, 0);
	cout << maxx << endl;
	return 0;
}

pichulia 4년 전 3

1 1 이면 연속된 3개의 계단을 밟은 꼴이 됩니다.

만약 step=4 였으면 path가 1 1이 될동안

step값은 5 6이 될 것입니다.

이는 4 5 6번 계단 3개를 밟은것이지요.

1 1 이 된다고 생각하신 이유로는 맨처음 계단(바닥)에서 1 1로 오르는 경우 때문인거같은데...

바닥에 서있는것은 계단을 밟은 것으로 취급되지 않기 때문에 이때만 예외입니다.

이 부분만 고치면 무사히 시간초과를 받으실 것입니다.

iamthejiheee 4년 전 0

와우........완전 틀린 로직이었네요

넘나리 감사합니다.

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

문제

문제

출처

ICPC

C++ 왜 틀린 로직일까요..

iamthejiheee 4년 전 0

pichulia 4년 전 3

iamthejiheee 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말