7964

 

static int solution(void)
{
	int N, D, ret = 0, off = 0;
	cin >> N >> D;

	int * ternel = new int[N + 2];
	ternel[0] = 1; ternel[N + 1] = 1;

	for (int i = 1; i <= N; i++)
		cin >> ternel[i];

	for (int i = 0; i + D < N + 1; i += off)
	{
		for (off = 1; off <= D; off++)
		{
			if (ternel[i + off]) //거리 D안에 차원관문이 존재.
				break;
		}

		if (off > D)
		{
			off = D;
			ret += 1; //차원 관문 설치
		}
	}

	delete[] ternel;
	return ret;
}

이 문제를 해결하기 위한 키 포인트 중 하나는 아래의 조건이었다.

모든 차원 관문 사이와 직접적으로 이동이 가능하도록 차원 관문을 재건하려고 한다.
(단, 0번 위치와 N+1번 위치에는 차원 관문이 존재 한다.)

 

그래서 x 지점에서 D 이내에 차원관문이 반드시 존재하게 끔 해야 한다는 것이다.

그래서 차원관문이 존재하는 지점으로 이동 하게 하는데, 이는 i += off 이다.

그래서 이 작업을 반복하게 되면 필요한 차원 관문 수를 구할 수 있다.

또, 이렇게 되었을 시 차원 관문 사이에 거리는 최대 D 이므로, 모든 도시에 갈 수 있다.

 

반복문 조건 시, i + D < N + 1 에서 N + 1 위치에는 차원 관문이 존재하기 때문에, N + 1 까지 갈 필요는 없으며,

더욱이 현재 위치 i 에서 거리 D 내에서는 반드시 차원 관문이 존재하게 설정 되기 때문에, 저 반복 조건이 성립하게 된다.