글 읽기 - [틀렸습니다] 4페이지까지 존재하는 모든 반례를 돌려보았습니다....

wony6731 4년 전 0

DP가 아닌 재귀로 먼저 풀어보려고 코드는 재귀로 짰습니다.

각 계단에 도착할때마다의 지금까지 합을 업데이트해주면서 값이 더 낮은 과정은 무시하도록 구현하였습니다.

어느 부분에서 틀렸을까요....?ㅜㅜ

반례라도 알 수 있을까요.. 열심히 게시판 4페이지까지 뒤져봤는데도 모든 반례가 잘 작동하네요...ㅜㅜ

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Node{
	int sum;
	int cnt;
	int idx;
};
int N;
vector<int> V;
queue<Node> Q;
int max_value = 0;
int visited[301];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++){
		int tmp;
		cin >> tmp;
		V.push_back(tmp);
		visited[i] = 0;
	}

	struct Node add;
	add.sum = 0;
	add.cnt = 0;
	add.idx = -1;
	Q.push(add);
	while (!Q.empty()){
		auto cur = Q.front();
		Q.pop();

		if (cur.idx == V.size() - 1)
			max_value = max(max_value, cur.sum);

		struct Node next;
		int next_idx = cur.idx + 1;
		// 한 계단	(1만 가능)
		if (next_idx >= V.size()) continue;
		if (cur.cnt <= 1){
			next.sum = cur.sum + V[next_idx];
			next.cnt = cur.cnt + 1;
			next.idx = next_idx;
			if (visited[next_idx] < next.sum){
				Q.push(next);
				visited[next_idx] = next.sum;
			}
		}

		// 두 계단
		next_idx = cur.idx + 2;
		if (next_idx >= V.size()) continue;
		next.sum = cur.sum + V[next_idx];
		next.cnt = 1;
		next.idx = next_idx;
		if (visited[next_idx] < next.sum){
			Q.push(next);
			visited[next_idx] = next.sum;
		}
	}

	cout << max_value << "\n";

	return 0;
}

surung9898 4년 전 2

반례는 다음과 같습니다.

/*
11
1
6
4
7
3
7
5
2
1
5
3

answer: 32
output: 31

wony6731 4년 전 1

역시 반례가 또 있었네요...ㅜㅜ 반례는 그런데 어떻게 찾으시는건가요? 저도 직접 찾아보고 싶은데..

surung9898 4년 전 3

제가 문제를 풀 때는 랜덤하게 생성한 테스트케이스를 직접 손으로 계산하여 출력결과와 비교합니다.

https://www.acmicpc.net/blog/v...

저 같은 경우 실력이 부족하여 질문에 대한 반례케이스 찾기도 비슷하게 하고있습니다. 질문자님의 코드와 제 정답코드를 임의의 테스트케이스를 만들어 출력결과를 비교하는 방식으로 찾습니다.

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

문제

문제

출처

ICPC

[틀렸습니다] 4페이지까지 존재하는 모든 반례를 돌려보았습니다....

wony6731 4년 전 0

surung9898 4년 전 2

wony6731 4년 전 1

surung9898 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말