2차식 정답 추측

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. 숫자 a의 최대값을 보면 19자리 이므로, Int64 자료형에 저장해야하는 것을 알 수 있음
2. f(x) = x ^ x + x 2차식을 곱셈 형태로 변형하게 되면, f(x) = x * (x + 1)
3. 즉, 자기 자신과 자신보다 1큰 수의 곱을 통해 a를 만들어내야 되는 것을 알 수 있음
4. 두 수의 곱을 통해 a를 얻어내야 하므로, 완전탐색을 하게 된다면 O(N)으로 문제를 해결할 수 없음
5. 따라서 이진탐색을 통해 0부터 a의 제곱근 + 1까지의 수를 x * (x + 1) 연산 함으로써 값을 얻어낼 수 있음

5. 전체 코드

//MARK: - 2차식 정답 추측

//MARK: - Framework
import Foundation

//MARK: - Function
func binarySearch(_ start: Int64, _ end: Int64, _ value: Int64) -> Int64 {
    if start + 1 >= end {
        return start
    }
    
    let x: Int64 = (start + end) / 2
    return x * (x + 1) <= value ? binarySearch(x, end, value) : binarySearch(start, x, value)
}

func solution() -> Void {
    //MARK: - Input
    guard let a: Int64 = Int64(readLine() ?? "0") else { return }
    
    //MARK: - Process
    let result: Int64 = binarySearch(0, Int64(sqrt(Double(a))) + 1, a)
    
    //MARK: - Output
    print(result)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.