1131번 : 숫자

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

1131번: 숫자

i부터 시작해서 나열되는 수들 중 가장 작은 수의 합을 구하는 문제이다.

 

아이디어 : 

그래프로 생각한다. 수 하나에서 시작하여 일정 수들을 거치면 항상 사이클이 생기는 것을 파악했다.

따라서 사이클에 속해있는 수들은 항상 똑같은 dp값을 가지고, 그게 아닌 수들만 따로 예외처리 해준다.

구현 : 

먼저 p배열엔 0~9의 K제곱을 저장해준다.

nxt엔 Sk(i)한 수들을 미리 저장해준다.

아이디어에 나와있듯, 사이클을 한번 찾으면, 다시 그 사이클을 돌면서 min값을 찾고, 한번 더 그 사이클을 돌면서 dp값을 min으로 채워준다.

코드 : 

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
ll dp[1000001]; // dp[i]:Sk(i)의 최소값
bool visit[1000001];
ll nxt[1000001];
ll p[10];
ll calc(ll x){
	if(x<=1000000 && nxt[x]) return nxt[x];
	ll ret=0;
	while(x){
		ret+=p[x%10];
		x/=10;
	}
	if(ret>1000000) return calc(ret);
	return ret;
}
void f(vector<ll> acc){
	ll cur=acc.back();
	if(!dp[cur] && visit[cur]){ // cur부터 시작하는 사이클을 이 사이클의 최솟값으로 모두 채움.
		ll tmp=nxt[cur];
		ll minn=cur;
		while(tmp!=cur){
			minn=min(minn,tmp);
			tmp=nxt[tmp];
		}
		dp[cur]=minn;
		tmp=nxt[cur];
		while(tmp!=cur){
			dp[tmp]=minn;
			tmp=nxt[tmp];
		}
		for(int i=acc.size()-1; i>=0; --i){
			if(!dp[acc[i]]){
				minn=min(minn,acc[i]);
				dp[acc[i]]=minn;
			}
		}
		return;
	}
	if(dp[cur]){
		ll minn=dp[cur];
		for(int i=acc.size()-1; i>=0; --i){
			if(!dp[acc[i]]){
				minn=min(minn,acc[i]);
				dp[acc[i]]=minn;
			}
		}
		return;
	}
	acc.push_back(nxt[cur]);
	visit[cur]=true;
	f(acc);
}
int main(){
	ll A,B,K; cin>>A>>B>>K;
	for(ll i=0; i<10; ++i){
		p[i]=pow(i,K);
		// cout << p[i] << '\n';
	}
	for(ll i=1; i<=1000000; ++i){
		nxt[i]=calc(i);
		// cout << "nxt["<<i<<"]="<< nxt[i] << '\n';
	}
	
	ll res=0;
	for(ll i=A; i<=B; ++i){
		if(!dp[i]) {
			vector<ll> temp;
			temp.push_back(i);
			f(temp);
		} 
		res+=dp[i];
	}
	cout << res << '\n';
	
}