ttobogims   10달 전

 안녕하세요~ 문제를 풀어봤지만 계속해서 틀렸다고 해서 질문을 남깁니다!

제가 문제를 푼 방법에 대해서 설명드릴께요

맨 왼쪽에서 맨 오른쪽으로 가야하는 최소 점프횟수를 구해야합니다.

1. 그러기 위해서는 내 위치에서의 값 array[start] 값이 만약에 0 이라면, 어느 곳으로도 점프를 할 수 없기에 flag=1로 만들어주고, 루프탈출.

flag=1인경우 " -1 "을 출력합니다.

2. 현재 위치 + array[start] 값이 N과 같거나 크게되면 도착할 수 있는 경우이므로 jump++; 해주고 루프를 탈출합니다.

3. 내 위치에서의 값 array[start] 만큼 오른쪽을 살피고 그 중 최대값을 가지는 칸으로 점프를 해줍니다(start값 갱신)


어떤 반례의 경우가 있는지 궁금하네요 ㅠㅠ 계속해서 만들어서 넣어봤는데 찾을 수가 없습니다.

game2k   10달 전

2. 현재 위치 + array[start] 값이 N과 같거나 크게되면 도착할 수 있는 경우이므로 jump++; 해주고 루프를 탈출합니다.

도착할 수 있는가를 찾는 것이 아니라 도착 했을 경우 그것이 최솟값인지를 확인해야 합니다.

3. 내 위치에서의 값 array[start] 만큼 오른쪽을 살피고 그 중 최대값을 가지는 칸으로 점프를 해줍니다(start값 갱신)

가장 멀리 점프할 수 있는 경로만 따라가는것은 그리디에 기반한 알고리즘으로 모든 경우를 전부 확인하는 DP와는 차이가 있습니다.

항상 가장 멀리 이동할 수 있는 칸만을 따라갈 경우 최솟값이 된다는 점을 증명하지 못하면 위 알고리즘은 정당성이 보장되지 않습니다.

본 문제에서 작성하신 그리디 알고리즘으로는 최솟값을 구할 수 없으므로, 위 알고리즘으로 찾은 경로보다 더 적은 점프 횟수로 이동 가능한 경우가 있을 수 있습니다. 모든 경우를 전부 고려하는 DP알고리즘을 작성해 보세요

game2k   10달 전

10

5 1 3 1 2 1 4 1 1 1

의 경우 답은 3 입니다. 일단 위 알고리즘의 경우 범위내에 같은 최댓값이 있을 경우  가장 뒤에있는걸 선택하지 않는다은 문제점이 있습니다.

그것을 고려한다 하더라도 위 알고리즘에서는 1 -> 3 -> 5 -> 7 -> 10 으로 4를 답으로 찾을 것입니다.

그러나 1 -> 6 -> 7-> 10 의 3번 점프하는 더 빠른 경로가 존재합니다.

ttobogims   10달 전

game2k 님 감사합니다!!~ ^^

다시 한 번 생각해서 문제를 풀어보도록 하겠습니다

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