백준 14399 2연산

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

10달쯤 전, 제가 알고리즘을 처음 시작했을 때 패기롭게 ‘한 명만 푼 문제’를 풀었었는데 그 문제가 바로 이 문제입니다. 이 문제를 풀고 알고리즘이 재밌다고 느끼게 되었던, 저에게는 매우 의미있는 문제입니다. 각설하고, 문제로 들어가죠.

1 이상의 수에서, 가장 나중에 나오는 알파벳은 “X”입니다. 어떤 수 a+b를 만드는 과정에서 a,b가 나왔다고 생각해 봅시다. X 연산을 수행해도 되고 Y 연산을 수행해도 되지만 사전순으로 앞에 나오는 연산을 하기로 했으므로 X 연산을 수행하는 것이 무조건 이득입니다.

(1은 연산을 할 필요가 없습니다. 예외로 처리 합시다.)

2연산의 과정을 거꾸로 생각해 보면 유클리드 호제법과 매우 닮아 있습니다. 20을 생각해보죠.

원래 과정 : (1,1) - (2,1) - (2,3) - (2,5) - (2,7) - (2,9) - (11,9) - (20,9)

역순 : 20 - (11,9) - (2,9) - (2,7) - (2,5) - (2,3) - (2,1) - (1,1)

20에서 (11,9)로 가는 마지막 연산 X를 제외하면 (11,9)의 유클리드 호제법과 모양이 완전히 일치합니다.

따라서 우리는 유클리드 호제법을 하면서 2연산의 길이를 구할 수 있습니다. (몫의 합)

유클리드 호제법의 시간복잡도가 O(log(n))이므로 가능한 모든 마지막 상태((1,n-1)~(n-1,1))를 다 해보아도 O(nlogn)의 시간복잡도로 가장 짧은 2연산의 길이를 구할 수 있습니다.

유클리드 호제법에서 최대공약수가 1이 아니면 (1,1)로 도달할 수 없기 때문에 최대공약수가 1이 아닌 경우는 제외해도 무방합니다.

나머지는 구현입니다.

#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
	return a%b?gcd(b,a%b):b;
}
int myf(int x, int y){
	if(x==1 && y==1) return 0;
	if(x==1 || y==1) return max(y-1,x-1);
	if(x>y) return myf(x%y,y)+x/y;
	else return myf(x,y%x)+y/x;
}
int main(void){
	int n; cin>>n;
	if(n==1){
		cout<<'\n';
		return 0;
	}
	int mn=n+5;
	vector<int> ans;
	for(int i=1;i<n;i++){
		if(gcd(i,n-i)!=1) continue;
		int xx=myf(i,n-i);
		if(mn>xx){
			mn=myf(i,n-i);
			ans.clear();
			ans.push_back(i);
		}
		else if(mn==xx) ans.push_back(i);
	}
	string mx_s="";
	for(int i=0;i<mn;i++) mx_s+="Y";
	for(int x:ans){
		int a=x,b=n-x;
		string tmp="";
		while(!(a==1 && b==1)){
			if(a>b){
				a-=b;
				tmp="X"+tmp;
			}
			else{
				b-=a;
				tmp="Y"+tmp;
			}
		}
		if(mx_s>tmp) mx_s=tmp;
	}
	cout<<mx_s<<"X";
	return 0;
}