[BOJ/C++] 17266 어두운 굴다리

문제

https://www.acmicpc.net/problem/17266

풀이

• 처음 시도
  굴다리 배열 0으로 초기화, cnt = 1로 시작해서 굴다리 배열이 전부 1될 때까지 cnt++
  
  ⛔문제점 : 굴다리 길이 : 7 / 가로등 위치 : 0, 5
  cnt=2면 굴다리 배열 전부 1이지만, 0~2, 3~7을 밝히므로 2-3 구간을 무서워서 못 지나감
  
  ✔️ 다른 방식의 접근 필요

• 참고한 풀이

  double형 max값 구하는 함수는 fmax

1. 맨 처음 가로등 : 굴다리의 거리만큼 밝혀야 함

2. 젤 끝 가로등 : (굴다리의 길이 - 끝 가로등의 위치)만큼 밝혀야 함

3. 각 가로등 사이 : ceil(가로등 사이의 길이 / 2)만큼 밝혀야 함
   
   이 중에 max 값 찾으면 됨

코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	vector<int> v(M);
	double h = 0;
	for (int i = 0; i < M; i++) {
		cin >> v[i];
	}

	if (M == 1)	h = N;
	else {
		h = fmax(v.front(), N - v.back());
		for (int i = 0; i < M - 1; i++) {
			h = fmax(h, ceil((v[i + 1] - v[i]) / 2.0));
		}
	}

	cout << (int)h;

	return 0;
}