[백준 11564] 점프왕 최준민 (C++)

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

문제

---

준민이는 점프를 좋아한다. 창영이는 그의 점프력을 시험하기 위해 수직선을 하나 놓고, a 이상 b 이하의 모든 정수 좌표에 맛있는 초콜릿을 놓았다. 수직선은 아래의 그림과 같이 나타낼 수 있다.

준민이는 항상 0에서 시작하며, 준민이의 점프력이 k 라면 한 번 점프를 하여 -k 나 +k 좌표에 도달한다. 준민이는 항상 점프 거리가 k가 되도록 점프를 한다. 만약 0의 위치에 초콜릿이 있다면, 준민이는 점프하기 전에 초콜릿을 일단 먹고 시작한다.

초콜릿 중독자인 준민이는 모든 초콜릿을 얻기 위해 수직선에 올라섰다. 또한 준민이는 아침에 밥을 아주 많이 먹었기 때문에 무한번 점프 할 수 있다. 여러분이 해야하는 일은, k의 점프력을 가진 준민이가 얻을 수 있는 초콜릿의 최대 개수를 구하는 것이다.

 

입력

---

입력은 한 줄로 구성된다. 준민이의 점프력 k (1 ≤ k ≤ 10¹⁸), 초콜릿이 존재하는 시작 좌표와 끝 좌표 a, b (-10¹⁸ ≤ a ≤ b ≤ 10¹⁸)가 공백으로 구분되어 정수로 주어진다.

 

출력

---

준민이가 무한 번 점프할 수 있을 때, 얻을 수 있는 초콜릿의 최대 개수를 구하여라.

 

문제 풀이

---

수학 문제.

 

a와 b의 범위를 적당히 나누어 분기 처리한다. 준민이의 점프력 k는 변하지 않으므로 k의 배수인 좌표(음의 값 포함)만 도달할 수 있다. 

만약 a가 0보다 크다고 가정해보자. (조건에 의해 b는 a보다 크거나 같다.) a~b 사이의 범위는 0부터 b까지의 범위에서 0부터 a-1까지의 범위를 제외한 것이라고 볼 수 있다. 0부터 b까지의 범위 중 도달할 수 있는 좌표는 b 이하의 0, k, 2k, 3k...이다. 따라서 (b / k) + 1개가 된다. 0부터 a-1까지의 범위 중 준민이가 도달할 수 있는 좌표는 a-1 이하의 0, k, 2k, 3k...이므로 a-1까지의 개수는 (a-1 / k) +1개가 된다. 즉, a~b 사이의 얻을 수 있는 초콜릿의 개수는 (b / k) - (a-1 / k)가 된다.

 

a가 0이라고 가정해보자. 0부터 b까지의 범위이므로 (b / k)+1이 된다.

 

a가 0보다 작다고 가정해보자. 이 경우는 b가 음수, 0, 양수임에 따라 구하는 방법이 달라진다.

b가 음수라면, a가 0보다 큰 경우인 상황을 좌우반전한 것과 같다. 큰 쪽이 a이고, 작은 쪽이 b가 되고, 개수 계산을 위해서는 음수를 양수로 변경해주어야 하므로  (-a / k) - (-b+1 / k)이 된다. 

b가 0이라면, a가 0인 상황을 좌우반전한 것과 같다. 따라서 (a/k)+1이 된다.

b가 0보다 크다면 a ~ -1, 0, 1 ~ b 세 개의 구간으로 나눌 수 있다. 따라서 정답은 -a/k + 1 + b/k가 된다.

 

아래는 코드.

 

#include <iostream>
using namespace std;

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

	long long K, A, B;
	cin >>K>> A >> B;
	if (A > 0)
	{
		cout << B / K - (A - 1) / K << "\n";
	}
	else if (A == 0)
	{
		cout << B / K + 1<< "\n";
	}
	else if (A < 0 && B < 0)
	{
		cout << -A / K - (- B -  1) / K << "\n";
	}
	else if (A < 0 && B == 0)
	{
		cout << -A / K + 1 << "\n";
	}
	else //A < 0 && B > 0
	{
		cout << B / K + (- A / K) + 1 << "\n";
	}
	return 0;
}