https://www.acmicpc.net/problem/18665
문제요약
- 처음에 0, 1, 2가 있음
- x^2 - y 연산으로 원소를 추가할 수 있음. 단 0 <= <= 10^18을 만족해야함
- 43번의 단계 안에 N을 만들어야함 (0 <= N <= 10^18)
- 단계를 최적화 할 필요는 없고, 조건을 만족하기만 하면 됨
접근법
- 43번의 단계에 안된다는 말은 없음. 어떤 숫자든지 만든다는 이야기
- 4도 바로 만들어 지고, 3도 바로 만들어짐
- 3* 3 = 9가 만들어지면 8, 7, 6, 5가 만들어짐
- 4 * 4 = 16이 만들어지면 15, 14, ... 10이 만들어짐
- 작은 것부터 하나씩 만들어가면 다 만들어지는 것 같음
- 최종 만들어야할 숫자는 N 인데 x^2 - y 형태에서 만들어질 것임
- 어떤 제곱수 - y 형태일텐데 가장 작은 제곱수를 찾아봄
- 그러면 숫자가 N -> x, y로 나뉘어질텐데, 작은쪽으로 탐색을 이어나감
- 즉 sol(N) : N -> x, y로 분해, 작은 것 부터 sol(x), sol(y) 수행, 다 수행 하고 나면 x, y를 집합에 추가
- 이렇게 하면 대략 작은 것부터 만들어나가는 것 같음
- x, y를 추가하는 시점에 출력
후기
- 왜 이게 되는지 모르겠다
newbieski