[백준] 1834. 나머지와 몫이 같은 수

: solved.ac - Bronze 1

 

https://www.acmicpc.net/problem/1834

1834번: 나머지와 몫이 같은 수

 

 

예제 입력 1

3

 

예제 출력 1

12

 

예제 입력 2

2000000

 

예제 출력 2

3999999999999000000

 

 

정답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	long long total = 0;
	int n;
	scanf("%ld", &n);

	for (long long i = 0; i < n; i++) {
		total += (n * i) + i;
	}
	printf("%lld", total);
	return 0;
}

 

---

해설

: 수학적 원리를 이용한다.

정수의 나누기에서 (나누는 수 * 몫) + 나머지 = 나눠지는 수 임을 이용한다.

여기서 같아야 하는 것은 몫과 나머지이고, 나머지는 반드시 나누는 수보다 작아야 하므로

1부터 (나누는 수-1)까지의 정수를 위 식의 몫과 나머지에 대입하여

계산된 피젯수를 하나의 변수에 합산한다.

 

	long long total = 0;
	int n;
	scanf("%ld", &n);

	for (long long i = 0; i < n; i++) {
    		total += (n * i) + i;
	}

 

단 이 문제에서 주의해야 하는 부분이 있다면 나누는 수가 200만까지 갈 수 있다는 것이다.

이 경우 합계를 저장하는 변수 total은 (200만*1 +1) 부터 (200만 * 199만9999 + 19만9999)의 수까지를

모두 합한 값을 담아야 하므로, long long int (unsigned일 필요는 없다) 형의 변수를 사용해야 함은 자명하다.

 

다만 total 변수에 합산하기 전의 우변의 식도 (200만 * 199만9999 + 19만9999) 만큼은 담아낼 수 있어야 하기 때문에

여기에서 오버플로우가 일어나서는 안 된다.

여러 번 변수의 형이나 순서 등을 바꿔 가며 실험해본 결과 for문의 변수 i도 long long 형이어야 함을 알아냈다.

(long 형도 안 된다. long long이어야 한다.)(n의 변수형은 무관하다.)

위와 같이 변수 자료형을 사용해 주면 문제없이 계산하고 결과값을 도출해낼 수 있다.