백준 1131번: 숫자

백준 온라인 저지(BOJ) 1131번 문제

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

1. 문제 요약

자연수 N이 주어졌을 때, N의 각 자리수를 K제곱한 뒤 더하여 수열을 만든다.

A, B, K가 주어졌을 때, A≤N≤B의 N으로 시작하는 수열에서 가장 작은 수의 합을 구하기

2. 알고리즘

쉬워보이는데 생각보다 까다롭다.

다이나믹 프로그래밍 문제인데,

A->B일 때

A로 시작하는 수열의 최솟값 = B로 시작하는 수열의 최솟값 / A 중 작은 값

이 성립한다.

모든 수열은 최종적으로 루프에 도달하게 되는데, 시간관계상 이 루프의 정보들만 미리 구한 뒤 넣어주었다.

합이 10억을 가뿐히 넘기므로 long long을 써야한다.

3. 코드

#include <iostream>
using namespace std;

int K;
int d[1000001] = { 0 };

int cal(int n) {
	int r = 0, t, u;
	while (n) {
		t = 1;
		u = n % 10;
		for (int i = 0; i < K; ++i) t *= u;
		r += t;
		n /= 10;
	}
	return r;
}

int minimal(int n) {
	if (n > 1000000) return minimal(cal(n));
	if (d[n] > 0) return d[n];

	int t = minimal(cal(n));
	return d[n] = t > n ? n : t;
}

int main() {
	int A, B;
	long long sum = 0;
	cin >> A >> B >> K;

	int a[7][20] = { { 0 },
				{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
				{ 1, 4 },
				{ 1, 371, 153, 55, 370, 160, 407, 919, 136 },
				{ 1, 1138, 8208, 2178, 1634, 9474 },
				{ 1, 24584, 9045, 10933, 9044, 244, 8299, 8294, 58618, 4150, 54748, 93084, 4151, 92727, 89883, 194979 },
				{ 1, 239459, 17148, 282595, 93531, 63804, 548834 } };
	
	int i = 0, n;
	while (a[K][i]) {
		n = a[K][i];
		do {
			if (n <= 1000000) d[n] = a[K][i];
			n = cal(n);
		} while (n != a[K][i]);
		++i;
	}

	for (int i = A; i <= B; ++i) {
		sum += minimal(i);
	}
	cout << sum << endl;

	return 0;
}