[백준/C++] 1081번. 합

문제

1081번: 합

---

1. 첫 번째 풀이

사고 과정

자릿수는 아래와 같은 특징이 있다.

• k + 1의 자릿수는 k의 자릿수의 합 + 1이다.

예를 들어 316의 자릿수의 합은 10으로, 315의 자릿수의 합인 9보다 1 큰 값이다.

 

이를 통해 L부터 U까지, 모든 자릿수의 합의 합을 구할 수 있는데

위와 같은 원리로 구할 수 있다.

 

하지만 여기엔 함정이 있는데,

이렇게 9 -> 0으로 넘어가는(꺾이는) 부분에서, 자릿수가 -9를 한다는 점이다.

(왜 -8이 아닌 -9냐면, 20은 원래 자릿수의 합이 11이어야 하는 자리기 때문.)

 

그럼, 이런 부분이 몇 개 존재하는가? 14와 53의 예시를 들어 살펴보자.

증가만 고려해 자릿수의 합을 구해둔 상태에서, 위 표만큼 빼주면 실제 답을 얻을 수 있다.

 

그 중 첫째 줄은 어차피 -0이니 무시하고, L을 20으로 만들어준다.

이는 일반화하면, P번째 자릿수(오른쪽 기준, 십의 자리라면 2번째)를 고르는 시점에서, P보다 작은 자릿수는 모두 0이며

P번째 자릿수는 L보다 1만큼 커야 한다.

 

말로 설명이 어려운데, P가 2일 때 14라면 20, 39라면 40, 172라면 180이다.

P가 3일 때 172라면 200이 된다.

이를 NL이라고 하자. (New L)

 

그럼 (U - NL + 1)개의 수는 9만큼 빼줘야하며, 이 값에서 10을 뺀 개수만큼 또다시 9를 빼줘야 한다.

 

14와 53의 예시라면 34개의 9를 빼주고, 24개의 9를 빼주고, 14개의 9를 빼주고, 4개의 9를 빼준다.

 

코드

#include <iostream>

int getSumOfPlace(int k) {
	int sum = 0;

	while (k > 0) {
		sum += k % 10;
		k /= 10;
	}

	return sum;
}

int main() {
	int l, u;
	std::cin >> l >> u;
	long long n = u - l;

	long long answer;

	answer = getSumOfPlace(l) * (n + 1);

	if (n % 2 == 0) {
		answer += ((n / 2) * (n + 1));
	}
	else {
		answer += (((n + 1) / 2) * n);
	}

	int d = 10;
	while ((u / d) > 0) {
		long long nl = ((l / d) + 1) * d;

		long long sub = u - nl + 1;

		for (; sub > 0; sub -= d) {
			answer -= 9 * sub;
		}

		d *= 10;
	}

	std::cout << answer;
}

 

그래서 이런 코드가 나왔고, 예제는 모두 통과했다.

 

결과

 

0과 2,000,000,000도 순식간에 풀어냈지만, 시간 초과에 걸렸다.

---

2. 두 번째 풀이

사고 과정

매 번 *와 -연산을 하는 게 문제였을까? 싶었는데, 그정도론 큰 차이가 생기지 않았다.

 

그렇담 역시 수학답게, 수식으로만 풀어야 하는 걸까?

 

질문 게시판을 (스포없이) 둘러보니, for문 자체가 안 돌아야 성공할 수 있을 거라 한다.

 

연속합과 비슷하게 생겨서, 이를 응용할 수 있나 싶었다.

 

그래서 문제를 좀 더 단순하게, 1부터 N까지의 자릿수 합의 합을 구하는 문제로 바꿔보았다.

(이러면 1부터 U까지, 1부터 L - 1까지 구한 후 둘을 빼면 된다.)

 

각 숫자의 자릿수 합은 이렇게 나타나지며

 

연속 합은 이렇게 나타난다.

 

솔직히 봐도 모르겠다. 빼는 9의 개수를 수식으로 구하는 게 더 빠를 듯...

 

그래서 빼는 9의 개수를 카운팅하는 방법을 바꿔봤다. 1부터 N까지라면, 예를 들어 53이라면

1부터 n까지의 합은 gaussSum이라는 함수로 정의했을 때

 

count = gaussSum(N - 1) * 10 + (N / 10) * (N % 10)

 

개가 나온다. 10을 d로 추상화하면 모든 자릿수에 대해 성립한다.

 

코드

#include <iostream>

unsigned long long gaussSum(int k) {
	if (k % 2 == 0) {
		return (k / 2) * (k + 1);
	}
	else {
		return ((k + 1) / 2) * k;
	}
}

unsigned long long getSumOfPlace(int n) {
	unsigned long long answer;

	answer = gaussSum(n);

	unsigned long long d = 10;
	unsigned long long count = 0;
	while ((n / d) > 0) {
		unsigned long long q = n / d;
		unsigned long long r = n % d;

		count += gaussSum(q - 1) * d + q * (r + 1);

		d *= 10;
	}

	answer -= 9 * count;

	return answer;
}

int main() {
	int l, u;
	std::cin >> l >> u;

	if (l < 1) {
		l = 1;
	}

	std::cout << getSumOfPlace(u) - getSumOfPlace(l - 1);
}

 

결과

 

이제 시간은 괜찮지만, 틀렸다고 나온다.

---

3. 마지막 풀이

사고 과정

0과 2,000,000,000이 얼만지 살펴봤는데 82,000,000,002가 나와야 한다고 한다. 내 코드는 18,446,689,532,315,481,090가 나온다.

 

따지고보니 더 이상했다. gaussSum(2,000,000,000)의 답은 2,000,000,000,000,000,000인데, 왜 저런 수자가 나온 걸까?

 

unsigned long long의 범위는 18,446,744,073,709,551,615로, 결코 범위를 넘지 않는다. 2로 먼저 나눈 후 곱하니 초과됐다가 돌아올 리도 없다.

 

그리고 내 실수를 찾았다. 매개 변수가 int 형이다.

 

C++은 (k / 2) * (k + 1)라는 식을 계산할 때, k가 int 형이면 int형 자료구조에 계산 결과를 담은 후 변수에 넣거나 반환하기에, 여기서 이상한 값이 들어갔다.

 

코드

#include <iostream>

unsigned long long gaussSum(unsigned long long k) {
	if (k % 2 == 0) {
		return (k / 2) * (k + 1);
	}
	else {
		return ((k + 1) / 2) * k;
	}
}

unsigned long long getSumOfPlace(unsigned long long n) {
	unsigned long long answer;

	answer = gaussSum(n);

	unsigned long long d = 10;
	unsigned long long count = 0;
	while ((n / d) > 0) {
		unsigned long long q = n / d;
		unsigned long long r = n % d;

		count += gaussSum(q - 1) * d + q * (r + 1);

		d *= 10;
	}

	answer -= 9 * count;

	return answer;
}

int main() {
	int l, u;
	std::cin >> l >> u;

	if (l < 1) {
		l = 1;
	}

	std::cout << getSumOfPlace(u) - getSumOfPlace(l - 1);
}

 

결과

 

드디어... 말 그대로 드디어 성공했다. (2시간 걸렸다.)

---

개선

사고 과정

예외 처리가 input에 걸리는 게 맘에 안 들어서 getSumOfPlace의 안으로 옮겼다. 좀 더 유연한 코드가 되었다.

왜 계속 Division by zero 에러가 뜨나 했더니, unsigned로 선언해서 그랬다. 일반 long long으로 바꿔줬다. (-1이 최댓값 - 1로 계산된 것)

 

q와 r 변수를 없애려다가, 가독성을 위해 남겨뒀다.

 

answer 선언과 값 할당이 분리되었는데(과거의 잔재), 이를 통합시켰다.

 

내친 김에 gaussSum의 if ~ else문도, 내가 자주 쓰던 얼리 리턴 형식으로 바꿨다.

 

코드의 명료성을 높이기 위해, 입력받는 l, u의 자료형을 long long으로 고쳤다. (암시적 형 변환이 사라졌다.)

 

count를 따로 세는 대신, 그때그때 answer에서 빼도록 변경했다.

 

코드

#include <iostream>

long long gaussSum(long long k) {
	if (k % 2 == 0) {
		return (k / 2) * (k + 1);
	}

	return ((k + 1) / 2) * k;
}

long long getSumOfPlace(long long n) {
	if (n < 1) {
		return 0;
	}

	long long answer = gaussSum(n);

	long long d = 10;
	while ((n / d) > 0) {
		long long q = n / d;
		long long r = n % d;

		answer -= 9 * (gaussSum(q - 1) * d + q * (r + 1));

		d *= 10;
	}

	return answer;
}

int main() {
	long long l, u;
	std::cin >> l >> u;

	std::cout << getSumOfPlace(u) - getSumOfPlace(l - 1);
}

 

리팩토링 할 게 별로 없을 줄 알았는데, 생각보다 많이 간결해졌다.

 

결과

 

코드도 그대로 정상 작동한다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/2655996

showhohxc님의 코드. 원리가 정말 궁금한데, 최악의 컨디션 때문에 문제 푸는 게 한계였다.

 

분석은 미래로 미뤄둬야겠다.

---

강평

수학 문제는 늘 어렵다. 정작 수학적 요소는 별 거 없는데도.

큰 수를 다룰 때, 반환값이나 변수 자료형을 틀려서 헤멘 적은 많아도, 매개 변수를 틀려 잘못 계산된 건 또 처음이다.

오랫동안 풀고 싶었던 문제였는데(같은 문제로 임시저장 한 글이 2개 더 있다.), 드디어 풀어서 너무 기쁘다.