글 읽기 - 30%에서 틀렸습니다.. 예외 케이스좀 부탁드려요

simm4256 6년 전 0

완전탐색으로 구현한 것 같은데 틀렸네요...

입력 개수가 1000개밖에 안되길래 이렇게 했는데

반례좀 찾아주세요 ㅠㅠ

#include <iostream>
using namespace std;

int s, arr[1001] = { 0, };

void BFS(int x, int sum, int c) {
	arr[x] = sum;
	if (x - 1 > 2 &&  (arr[x - 1] == 0 || sum + 1 < arr[x - 1]))
		BFS(x - 1, sum + 1, c);
	if (x + c < 1001 &&  (arr[x + c] == 0 || sum + 1 < arr[x + c]))
		BFS(x + c, sum + 1, c);
	if (x + x < 1001 && (arr[x + x] == 0 || sum + 2 < arr[x + x] < arr[x + x]))
		BFS(x + x, sum + 2, x);
}

int main() {
	cin >> s;
	arr[1] = 1;
	BFS(2, 2, 1);
	cout << arr[s];
}

koosaga 6년 전 0

앞 댓글은 착각한게 있어서 지웠습니다

12번째 줄이 이상한거 같은데 확인해보세요

simm4256 6년 전 0

아아 저런 실수가 있었네요

하지만 수정해도 그대로 틀리네요..

#include <iostream>
using namespace std;

int s, arr[1001] = { 0, };

void BFS(int x, int sum, int c) {
	arr[x] = sum;
	if (x - 1 > 2 && (arr[x - 1] == 0 || sum + 1 < arr[x - 1]))
		BFS(x - 1, sum + 1, c);
	if (x + c < 1001 && (arr[x + c] == 0 || sum + 1 < arr[x + c]))
		BFS(x + c, sum + 1, c);
	if (x + x < 1001 && (arr[x + x] == 0 || sum + 2 < arr[x + x]))
		BFS(x + x, sum + 2, x);
}

int main() {
	cin >> s;
	arr[1] = 1;
	BFS(2, 2, 1);
	cout << arr[s];
}

koosaga 6년 전 0

어떤 점에 최적보다 더 늦게 도착해도, 클립보드에 원소가 많다면 실제로는 그게 더 이득일 수도 있습니다

simm4256 6년 전 0

감사합니다.

일단 맞긴 맞았는데, 뭔가 어거지로 푼 느낌이네요.

제 원래 코드로 1000까지 돌렸을 때 최대치가 30보다 작길래

소스를 이렇게 수정하니 맞아버렸네요;;

다른 방법으로 풀어봐야겠습니다.

https://www.acmicpc.net/source...

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

문제

문제

출처

ICPC

30%에서 틀렸습니다.. 예외 케이스좀 부탁드려요

simm4256 6년 전 0

koosaga 6년 전 0

simm4256 6년 전 0

koosaga 6년 전 0

simm4256 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말