SWEA 16800번: 구구단 걷기 (D3)

SWEA 16800번

당신은 무한히 많은 행과 열이 있는 곱셈표 위에 서 있다. (i, j)셀에는 정수 ixj 가 적혀 있다. (만약 행과 열이 9개라면 이는 구구단 표와 동일하다.) 현재 당신의 위치는 셀 (1, 1) 이다. 당신은 곱셈표의 오른쪽이나 아래쪽 방향으로 이동할 수 있다. 즉, 당신이 (i, j)에 서 있다면, (i+1, j)나 (i, j+1)로 이동할 수 있다. 정수 N이 주어질 때, N이 적혀 있는 어떤 셀에 도착하기 위해서 최소 몇 번 움직여야 하는가?   [입력] 첫 번째 줄에 테스트 케이스의 수 TC가 주어진다. 이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.  l 첫 번째 줄에 정수 N이 주어진다. (2 <= N <= 10^12)     [출력] 각 테스트 케이스 마다 한 줄씩 문제의 정답을 출력하라.

#include <stdio.h>
#include <stdlib.h>
#define maxsize 10000

int main() {
	int tc;
	int i, k;
	long long int factor[maxsize], N, min, j;

	scanf("%d", &tc);

	for (i = 0; i < tc; i++) {
		k = 0;
		scanf("%lld", &N);

		for (j = 1; j*j <= N; j++) {
			if (N%j==0) {
				factor[k++] = j;
			}
		}
		min = N / factor[k - 1] + factor[k - 1] - 2;


		printf("#%d %lld\n", i + 1, min);
	}
	

	return 0;
}

실행결과

문제의 핵심은 크기가 큰 정수를 입력받는 것이므로

long long int 를 이용하는 것이었다.

 

이 문제는 단순한 소인수분해 문제였는데,

일반적으로 자연수 N에 대해 인수는 루트 N이하이므로,

인수를 확인하기 위해서 루트 N까지만 확인하면 시간복잡도를 줄일 수 있다.