2회 문제풀이 12 / ABC 144 C - Walk on Multiplication Table
ABC 144 C - Walk on Multiplication Table
【문제 개요】
타카하시군은 무한히 넓은 곱셈표 위에 있습니다. 곱셈표의 칸 (i, j)에는 정수 i x j가 적혀있으며, 타카하시군은 최초 (1, 1)에 있습니다.
타카하시군은 한번 이동에 (i, j)에서 (i + 1, j)나 (i, j + 1)중에서 어디로 이동할 수 있습니다.
정수 N이 주어질 때, N이 쓰여진 칸으로 도달하기 위해 필요한 이동 횟수의 최소값을 구하시오.
힌트 : 이진 탐색 알고리즘
【전제】
- 2 ≦ N ≦ 10^12
- 입력받을 모든 수는 정수이다.
【입력 형태】
1
N
【출력 형태】
정수 N이 적혀있는 칸에 도달하기 위해 필요한 이동횟수의 최솟값을 출력하시오.
【예시】
입력 예 1
1
10
출력 예 1
1
5
5회 이동으로 (2, 5)에 도달하는 것이 가능합니다. 5회 미만으로 이동할때는 10이 적혀있는 칸으로 이동하는것은 불가능합니다.
입력 예 2
1
50
출력 예 2
1
13
13회째 이동으로 (5, 10)에 도달하는것이 가능합니다.
입력 예 3
1
10000000019
출력 예 3
1
10000000018
ABC 144 C - Walk on Multiplication Table
【문제 개요】
타카하시군은 무한히 넓은 곱셈표 위에 있습니다. 곱셈표의 칸 (i, j)에는 정수 i x j가 적혀있으며, 타카하시군은 최초 (1, 1)에 있습니다.
타카하시군은 한번 이동에 (i, j)에서 (i + 1, j)나 (i, j + 1)중에서 어디로 이동할 수 있습니다.
정수 N이 주어질 때, N이 쓰여진 칸으로 도달하기 위해 필요한 이동 횟수의 최소값을 구하시오.
힌트 : 이진 탐색 알고리즘
【전제】
- 2 ≦ N ≦ 10^12
- 입력받을 모든 수는 정수이다.
【입력 형태】
1
N
【출력 형태】
정수 N이 적혀있는 칸에 도달하기 위해 필요한 이동횟수의 최솟값을 출력하시오.
【예시】
입력 예 1
1
10
출력 예 1
1
5
5회 이동으로 (2, 5)에 도달하는 것이 가능합니다. 5회 미만으로 이동할때는 10이 적혀있는 칸으로 이동하는것은 불가능합니다.
입력 예 2
1
50
출력 예 2
1
13
13회째 이동으로 (5, 10)에 도달하는것이 가능합니다.
입력 예 3
1
10000000019
출력 예 3
1
10000000018