[BOJ 27231, 약간 어려움] 2023년이 기대되는 이유 (C++)

개인적인 난이도

약간 어려움

 

정석 풀이는 아마 백트래킹으로 문자열 중간에 +를 삽입하는 것이다

근데그냥 브루트포스로 풀어도 풀린다
난 백트래킹 말고 그냥 set 반환하는 재귀함수 만들어서 브루트포스로 풀었다

재귀는 항상 어렵다 dp문제를 풀때도 항상 느끼지만 어떤 연산을 절차적으로 생각하는 건 익숙하지가 않다
그래서 한참 걸려서 풀었다 1시간정도걸림

수련이 부족하다

 

 

---

성공한 풀이)

 

성공한 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;
ll pow(int a,int b){
	if(a==0)return 0;
	if(a==1)return 1;
	if(b==0)return 1;
	return a*pow(a,b-1);
}
set<ll> sdsum(string str){
	set<ll> s;s.insert(stoi(str));
	for (int i = 1; i < str.length(); i++)
	{
		set<ll> tmps = sdsum(str.substr(i));
		for (ll j:tmps)
		{
			s.insert(stoi(str.substr(0,i))+j);
		}
	}
	return s;
}
int main(void) {
	fastio;
	int T;cin>>T;
	while (T--)
	{
		string s;cin>>s;
		int flg = 0;
		for (int i = 0; i < s.length(); i++)
		{
			if(s[i]-'0'>=2)flg=1;
		}
		if(!flg){
			cout<<"Hello, BOJ 2023!\n";
			continue;
		}
		set<ll> sums=sdsum(s);
		int cnt = 1;
		for (int i = 2; i < 10; i++)
		{
			ll m = 0;
			for (int j = 0; j < s.length(); j++)
			{
				m+=pow(s[j]-'0',i);
			}
			if(sums.find(m)!=sums.end())cnt++;
		}
		cout<<cnt<<"\n";
	}
	return 0;
}

 

핵심

1. 0 과 1로만 이루어진 입력이 들어올 경우 헬로백준을 출력하도록 예외처리를 해준다
2. 거듭제곱 연산은 하면 할수록 수가 빠르게 커진다. 오버플로우에 주의해야 한다 (9^10 = 3^20 ~= 35억)
   이 문제에서는 거듭제곱을 그렇게 많이 할 필요도 없다.
3. 숫자들을 쪼개서 더하기 할 수 있는 모든 경우를 검사해야 하므로, set을 이용한다

 

개선점

1. pow를 log(N) 시간복잡도로 구현 가능함 (분할정복) 
   https://www.techiedelight.com/ko/power-function-implementation-recursive-iterative/
2. string.substr() 와 stoi()를 남발 + 브루트포스 로 풀었더니 실행속도가 느림
3. 거듭제곱을 9승까지 계산할 필요도 없음. 거듭제곱의 합이 input보다 커질때 루프를 탈출하면 더 빠름
4. set 내에 원소가 있는지 파악할 때, set.find()보단 set.count()를 이용하는 것이 훨씬 간결하다

 

나중에 알아볼 부분

다 풀고 나서 친구 코드를 참고해봤는데, 생소한 count_if 함수를 통해 STL의 특정 원소 개수를 빠르게 체크 가능하다
근데 함수의 인자로 무려 람다함수를 받는다.

함수를 잘 쓰면 코드를 간결하게 짜기 편하다 (어떤 조건에서 루프 여러개를 한번에 탈출해야 하는 경우 break로는 탈출할 수 없다. 그래서 평소에는 함수를 따로 구현하거나, flg라는 변수를 만들어 flg가 1이면 루프를 탈출하는 식으로 구현했다. 아니면 goto를 쓰는 방법도 있다)

근데 람다함수를 쓰면, 풀이 중 딱 한번 쓸 함수를 굳이 길게 구현하지 않아도 됨. 알아두면 유용하게 쓸 것 같다