[백준알고리즘] 11060번: 점프 점프 -C++

[백준알고리즘] 11060번: 점프 점프 -C++

11060번: 점프 점프 (acmicpc.net)

11060번: 점프 점프

동적 계획법 문제다. 그렇게 어렵게 풀지는 않았으나, 생각지도 못한 반례가 있었어서 살짝 시간을 썼다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

재환이가 이동할 수 있는 칸만큼 오른쪽으로 이동하면 된다. 

 

처음에 이 문제에서 놓쳤던 반례는 1x1 크기의 미로에 갇힌 경우도 있을 수 있다는 것이다. 이 부분을 고치고 나니 문제를 해결할 수 있었다.

 

추가적으로, 해당 칸으로 점프를 못했는데, 그 칸에서 다음 칸으로 점프하는 경우를 세주지 않도록 주의해야 한다.

 

아래의 코드에서 \(count\)는 각 칸에 도착하기에 필요한 최소 점프 횟수를 의미하며, \(jump\)는 입력으로 주어지는 각 칸에서 점프를 뛸 수 있는 최대 길이다.

 

#include <iostream>
#include <vector>

void Solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	
	Solve();
}

void Solve(void)
{
	int n;
	std::cin >> n;

	std::vector<int> jump;
	for (int i = 0; i < n; i++)
	{
		int tmp;
		std::cin >> tmp;
		jump.push_back(tmp);
	}

	if (n == 1)
	{
		std::cout << 0;
		return;
	}

	std::vector<int> count(n);
	std::fill_n(count.begin(), n, -1);
	count[0] = 0;
	for (int i = 0; i < n - 1; i++)
	{
		if (count[i] < 0)
			continue;

		int distance = jump[i];
		for (int d = 1; d <= distance; d++)
		{
			if (n <= i + d)
				break;
			if (0 < count[i + d])
				continue;
			count[i + d] = count[i] + 1;
		}
	}

	std::cout << count[n - 1];
}