글 읽기 - dp 가 아닌 방식으로 구현했는데 오류가 있을까요??

d252b 6년 전 0

각 index에서 점프 할 수 있는 거리 중 가장 멀리 점프 할 수 있는 것을 골랐습니다.

예를 들어,

2 1 5 4 2 이고 index가 1부터 시작한다면

index 1 에는 2가 있으므로, index 2와 3까지 갈 수 있는데,

index + arr[index] 의 값이 가장 큰 값 (즉, 다음 장소에서 가장 멀리 까지 갈 수 있는 곳을 선택)

해서 index 3을 선택하는 방식으로 구현하였는데, 틀렸다고 뜨네요...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> arr;
int T;
int cnt = 0;
int main()
{
	scanf("%d", &T);
	arr.resize(T + 1, 0);
	for (int i = 1; i <= T; i++)
		scanf("%d", &arr[i]);

	int index = 1;
	int temp;
	int flag = 0;
	while (index < T)
	{
		int M = -1;
		for (int i = index+1; i <= index + arr[index]; i++)
		{
			if (i > T)		// 배열 index를 넘어 가는 경우
			{
				flag = 1;
				break;
			}
			if (M < i + arr[i])
			{
				M = i + arr[i];
				temp = i;
			}
		}

		if (arr[index] == 0)
		{
			printf("-1");
			return 0;
		}

		cnt++;
		index = temp;

		if (flag == 1)
			break;
	}
	printf("%d", cnt);
}

jh05013 6년 전 0

가능한 한 멀리 뛰는 것이 최적이 아닙니다.

5
2 3 1 1 0

d252b 6년 전 0

제 코드에서 23번 라인에 등호를 추가해주니 맞았습니다.

@jh05013님 답변 감사합니다.

다만 제가 짠 코드는 현재 자리에서 가장 멀리 뛰는 것이 아닌, 현재 자리에서 뛸 수 있는 후보군 중에 가장 멀리 뛰는 것을 선택한다는 의미였습니다.

즉 2 3 1 1 0 이고, index가 1부터 시작한다면

index 1번부터 시작해서 2번 ,3번까지 갈 수 있고,

여기서 가장 멀리 뛸 수 있는 것은 2번이므로 index 2를 선택해 나간다는 의미였습니다.

jh05013 6년 전 0

앗 그렇군요. 그 방법은 맞는 것 같습니다.

tofuprofessor1995 6달 전 0

1 1 2 9 1 ...

이런식으로 따지면 2에서 1로 뛰는게 가장 멀리 뛰는 건데 9로 뛰는게 최종적으로 가장 높지않을까요 ㅇㅅㅇ.. 그리디는 안되는 것 같고 dp이용해서 풀어야 하는 것 같습니다.

그럴거면 왜 bfs에 카테고리했는지 -ㅅ-. 시간만 괜히 날렸네요.

jh05013 6달 전 0

bfs로도 풀 수 있습니다.

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

문제

문제

출처

ICPC

dp 가 아닌 방식으로 구현했는데 오류가 있을까요??

d252b 6년 전 0

jh05013 6년 전 0

d252b 6년 전 0

jh05013 6년 전 0

tofuprofessor1995 6달 전 0

jh05013 6달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말