1103 Integer Factorizatio

The K−P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K−P factorization of N for any positive integers N, K and P.
Input Specification: Each input file contains one test case which gives in a line the three positive integers N (≤400), K (≤N) and P (1
Output Specification: For each case, if the solution exists, output in the format:
N = n[1]^P + … n[K]^P
where n[i] (i = 1, …, K) is the i-th factor. All the factors must be printed in non-increasing order.
Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 12 ​2 ​​ +4 ​2 ​​ +2 ​2 ​​ +2 ​2 ​​ +1 ​2 ​​ , or 11 ​2 ​​ +6 ​2 ​​ +2 ​2 ​​ +2 ​2 ​​ +2 ​2 ​​ , or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen – sequence { a ​1 ​​ ,a ​2 ​​ ,⋯,a ​K ​​ } is said to be larger than { b ​1 ​​ ,b ​2 ​​ ,⋯,b ​K ​​ } if there exists 1≤L≤K such that a ​i ​​ =b ​i ​​ for i ​L ​​ >b ​L ​​ .
If there is no solution, simple output Impossible.
Sample Input 1: 169 5 2
Sample Output 1: 169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2
Sample Input 2: 169 167 3
Sample Output2: Impossible 인터넷에 dfs가 일색입니다. 이게 바로 사나이일 수도 있습니다. dfs가 어렵다고 말하는 것도 아니고 스스로 그런 쪽으로 생각하지 않습니다. 물론 생각할 수 있다는 것과 생각할 수 있고 익숙하게 할 수 있다는 것은 다릅니다.저는 시뮬레이션을 사용했습니다. 22점입니다. 두 군데 오류가 있습니다. 하지만 저는 찾을 수 없습니다. 22점은 시험에서 이 점수가 될 수 있습니다. 하지만 제가 어디가 틀렸는지 모르면 괴로워요. 그리고 인터넷에서 테스트 포인트 2, 5를 찾았습니다. 그리고 실질적인 오류도 찾지 못했습니다. 그리고 알고리즘 노트에 있는 방법을 배웠습니다. dfs
첫 번째 22분 시뮬레이션은 p>2를 봤기 때문에 저는 최대 멱이 sqrt(n)라고 생각합니다. 그리고 조금씩 시뮬레이션, 감법, 판단을 했습니다. 저는 합리적이라고 생각합니다. 유일한 부족은 시간이 비교적 길고 알고리즘도 없고 가지치기도 없습니다. 사실 대체적으로 저는 dfs와 차이가 많지 않다고 생각합니다.

#include
#include
#include
#include
#include
#include
using namespace std;
vector<int> ans;
int power(int a,int b){
	int t = 1;
	for(int i=1;i<=b;i++){
		t*=a;
	}
	return t;
}
int main(){
	int n,k,p,maxn = 0;
	cin>>n>>k>>p;
	int sqt = (int)sqrt(n);
	for(int i=sqt;i>=1;i--){
		vector<int> temp;
		int tn = n,tmaxn=0;
		for(int t= i;t>=1;t--){
			while(power(t,p) <= tn){
			tmaxn+=t;
			tn -= power(t,p);
			temp.push_back(t);
			}
		}
		if(tn == 0 && tmaxn > maxn && temp.size() == k ){
			
			maxn = tmaxn;
			ans = temp;
		}
	}
	if(ans.size() == 0) cout<<"Impossible"<<endl;
	else{
		printf("%d = ",n);
		for(int i=0;i<ans.size();i++){
			if(i > 0) printf(" + ");
			printf("%d^%d",ans[i],p);
		}
	}
	return 0;
} 

두 번째 알고리즘 노트 dfs(내 자신의 깨달음, 비교적trash)는 먼저 오프라인으로 파워(i,p)를 기록한다. 가장 큰 것은 n을 초과하지 않고 파워 함수를 쓰는 것이 좋다. dfs는 가지를 자르는 것을 배운다.

// 
if(nowk == k && sum == n ){
		if(facsum > maxn){
			maxn = facsum;
			ans = temp;
		}
		return ;
	}
 
if(nowk == k && sum == n && facsum > maxn){
			maxn = facsum;
			ans = temp;
		return ;
	}

작은 디테일, 위의 방법은 더 많은 가지를 잘라낸다. 생각해 보면 이 문제는 내가 잘 생각한다. 즉, 문제에 대한 발굴, 이해, 그리고 dfs의 작법도 얻었다.

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n,k,p;
vector<int> fac,ans,temp;
int power(int b){
	int t = 1;
	for(int i=1;i<=p;i++) t*=b;
	return t;
}
void init(){
	int i = 0,temp = 0;
	while(temp <= n){
		fac.push_back(temp);
		temp = power(++i);
	}
}
int maxn = -1;
void dfs(int index,int nowk,int sum,int facsum){
	if(nowk == k && sum == n){
		if(facsum > maxn){
			maxn = facsum;
			ans = temp;
		}
		return ;
	}
	if(nowk > k || sum > n) return;
	if(index >= 1){
		temp.push_back(index);
		dfs(index,nowk+1,sum+fac[index],facsum+index);
		temp.pop_back();
		dfs(index-1,nowk,sum,facsum);
	}
}
int main(){
	cin>>n>>k>>p;
	init();
	dfs(fac.size()-1,0,0,0);
	if(maxn == -1) cout<<"Impossible"<<endl;
	else{
		printf("%d = ",n);
		for(int i=0;i<ans.size();i++){
			if(i > 0) printf(" + ");
			printf("%d^%d",ans[i],p);
		}
	}
	return 0;
} 

ffs도 앞으로 강화해야 할 부분인데 사실 그렇게 많은 문제를 만들었어요. 처음처럼 갑급을 두려워하는 문제는 생각하지 않았어요. 틀에 박힌 것을 파악하고 못하는 것을 먼저 생각하고 다른 사람의 우수한 사고방식과 알고리즘을 참고한 다음에 스스로 기억하고 이해하는 것이 가장 좋은 거예요. 그리고 자신의 것이 될 거예요. 조급해하지 마세요. 중요한 것은 효율과 견지예요. 응응, 계속 힘내세요.