20444 색종이와 가

PS 짬통/골랜디

kimximya 2023. 9. 21. 23:07

20444번: 색종이와 가위

첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1)

www.acmicpc.net

한대 얻어 맞았다

태그 까고도 못풀진 않았는데, 아무튼 결국 태그를 까긴 했다

골랜디의 장점을 느낄 수 있는 부분이었다, 자기가 약한 문제 나오면 질 수 밖에 없는 구조고

그 부분을 경험을 통해서 채워준다

수학적 규칙은 한 10분만에 찾긴 했다

2 * n ,

3 * (n-1)

4 * (n-2)

...

일반화 시키자면,

K의 약수 A, B가 있고

A*B = K를 만족할 때

A+B = N+2 를 만족하면 된다

그런데 이게 O(N)은 시간초과가 나고

O( sqrt(K) ) 도 O(N) 이랑 시간이 같다

그래서 결국 뭐여 씨발 하고 태그를 깠고

이분탐색이 나왔다

이분탐색도 안푼지 오래되서 구현 자체에서 많이 해맸다

아무튼 결론은 1~N 에서 이분탐색으로 위의 조건을 만족하는 해를 찾으면 된다