문제 설명
1, 2, 3, 4, ...., n 까지 숫자를 나열할 수 있다.
연속한 숫자들끼리 연결할 수 있는데 한번 연결하면 끝이고 다시 연결할 수 없다. 게다가 순서도 1 -> 2 -> 3 -> ... 순서대로 연결함
그래서 예를 들어 n이 5라면
1 - 2, 3, 4
2 - 3, 4
3 -4
이렇게 연결할 수 밖에 없다.
그래서 문제는 이런 연결들의 개수 중 가장 중간에 있는 연결이 어떤 것인지 측정하는 것이다.
5를 예로 들면 연결은 총 3 + 2 + 1해서 6개가 되는데 그 중 중간 값인 3이 1 - 4이므로 1이 답이 된다.
생각할 점
하.... 또 입력 범위가 10^9이다.
이분탐색으로 풀어야 한다.
---
이분탐색! 을 써야 겠다는 이해했는데 범위랑 n이 너무 헷갈렸다..
n이 6이라고 가정하면 1, 2, 3, 4, 5 이렇게 숫자가 있을거고 (연결하지 못하는 6은 제외하자)
각 연결은
1 - 2, 3, 4, 5, 6
2 - 3, 4, 5, 6
3 - 4, 5, 6
4 - 5, 6
5 - 6
이렇게 되어 있을 것이다. 연결 개수를 보면
1 - 5
2 - 4
3 - 3
4 - 2
5 - 1
이렇게 되어 있는데 이걸 쭉 나열해보자
1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5
여기서 l, r, mid 값을 어떻게 둘지 너무 어려웠다.. ㅠ 지금은 다 풀었으니 알겠는데 처음 볼 때 이거 값을 어떻게 두지 계속 고민했음 악악
암튼,,, 1, 2, 3, 4, 5 중 하나를 선택해서 그 숫자의 범위가 중간 값인지 계산해야 한다.
1, 1, 1, ... 이 숫자들의 합이 15라서 중간값인 7이 어느 범위에 있는지 확인해야 함.
먼저 l을 1 r을 5로 잡자. 여기서 중간 값이 3이라 3의 범위에 구하는 수 7이 있는지 확인한다.
3의 범위는 10, 11, 12라서 (하... 범위 구하는 것도 어려웠다) 7은 여기에 속해있지 않다.
그럼 이제 범위를 [1, 2]로 옮긴다 그럼 중간값은? 1임 1의 범위는 1, 5이다. 그러면 7은? 또 안 속함
그럼 범위는 정해졌다. 2임 따란
후... 이렇게 구했다... 이분탐색 어려워함 + 범위 어떻게 잡을지 모름 = 와장창...
그래도 뭐... 풀었으니깐... 성장했겠지. 열심히 하자는 마음으로 정리라도 해본다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;
int main() {
i64 n;
scanf("%lld", &n);
i64 l = 1;
i64 r = n - 1;
i64 calc = (n * (n - 1) / 2 + 1) / 2;
// printf("calc : %d\n", calc);
while (l <= r) {
i64 mid = (l + r) / 2;
i64 start = (mid - 1) * n - (mid - 1) * mid / 2 + 1;
i64 end = start + (n - mid) - 1;
// printf("l : %d r : %d mid :%d start: %d, end: %d\n", l, r, mid, start, end);
if (calc < start)
r = mid;
else if (end < calc)
l = mid;
else {
printf("%lld\n", mid);
return 0;
}
}
printf("%lld\n", l);
return 0;
}범위는 적당히 규칙 보고 찾았다.
아 처음에 중간값 구할 때 실수한 게 있다. 그냥 전체 합에서 절반이라 생각해 n * (n - 1) / 4라고 했는데 이러면 3을 넣으면 2가 나와야 하는데 1이 나온다. 제출하니 애매하게 46에서 틀렸는데 이게 원인이었다.
i64 calc = (n * (n - 1) / 2 + 1) / 2;
왜 이렇게 바꿨는지 이해도 못하고 일단 썼지만 다시 한번 생각해보았다.
아하
이게 1부터 시작해서 숫자 범위가 늘어났다. 그래서 내림을 해주면 안 되고 올림을 해줘야 했다. 그렇구나... 신경써줘야할게 왜이리 많지 헝..
그래도 끝냈다. 휴