백준 17451번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	1024MB	실버 3

---

풀이

 v의 최댓값이 매우 크기 때문에 당장 떠올린 풀이는 이분탐색이었다. 어떤 mid값에서 각 행성의 정수배수로 줄여가면서 최종적으로 행성을 모두 통과할 수 있는지를 구하면 된다.

 

이때 속도의 최댓값이 10^9이라고 int형을 써선 안된다. 10^9의 정수배도 연산하는 과정에서 들어갈 수 있고, 정답도 10^9 이하라고 한 적은 없기 때문에 이분탐색의 최댓값과 자료형에 주의해야한다. log(long long의 최댓값) ≒ 18이기에 적당히 10^18을 최댓값으로 사용했다. 어짜피 이분탐색을 하면 최댓값을 저렇게 줘도 연산은 70번을 넘지 않으니 넉넉하게 잡았다.

코드

#include <bits/stdc++.h>
using namespace std;
using ll = uint64_t;

int n;
vector<ll> dist;

void input() {
	cin >> n;
	dist.resize(n);
	for(ll& d : dist) cin >> d;
}

bool check(ll velo) {
	for(ll d : dist) {
		if (velo < d) {
			return false;
		}
		velo -= velo % d;
	}
	return true;
}

void sol() {
	ll low = 1, high = 1e18, mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (check(mid)) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	cout << low;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	input();
	sol();
}

 

풀이2

사실 자료형과 최댓값 문제를 간과하고 찾지 못해 인터넷을 검색해보았다. 그런데 대부분 그리디로 풀이를 하고 있었다. 글을 8개정도 열어본거 같은데 단 한개의 글에서만 이분탐색도 설명하고 있었고, 내가 간과한 자료형과 최댓값 문제를 설명해주었다.

 

 그리디로 풀이를 하는 과정은 역추적하는 것이다. 맨 뒤에서부터 속도를 계속 올려보는거다. 확실히 풀이가 더 쉬울 것 같긴 하나, 이분탐색도 좋은 풀이라고 생각한다.