백준 2231번 분해합 c++

 

문제 링크: https://www.acmicpc.net/problem/2231

 

 

 

 

간단 회고:

	O	X
내가 직접 풀었나?	✔
다른 사람 풀이를 참고 하였나?		✔
어려웠나?		✔
푸는데 오래걸렸나?	✔

✅✔

 

 

 

 

내 풀이:

 

#include <iostream>
#include <cmath> // std::abs
#include <array>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
int main()
{
  int input, temp_n;

  cin >> input;

  vector<int> vec;

  for (int i = 1; i < input; i++)
  {
    temp_n = i;
    while (temp_n != 0)
    {
      vec.push_back(temp_n % 10);
      temp_n /= 10;
    }

    int sum = accumulate(vec.begin(), vec.end(), 0);

    if (sum + i == input)
    {
      cout << i;
      return 0;
    }

    vec.clear();
  }

  cout << 0;
  return 0;
}

 

여러가지 시간 단축을 할 수있는 경우의 수를 처음부터 고려하다보니 오히려 진도가 나가질 않았다.

 

따라서 아예 모든 경우의 수를 수행하게 진행하였다. 

 

라이브러리중에선 vector의 동적 리스트와 (인풋된 수의 길이에 따라 런타임중 리스트 길이가 달라져야하기에) numeric에서 accumulate라고하는 특정 주소 범위의 원소들을 합해주는 함수를 사용했다.

 

 

 

참고한 타 풀이 및 출처(있다면)

출처:https://j3sung.tistory.com/221

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
 
int main(int argc, char *argv[])
{
	int num;
	int sum;
	int part;
 
	cin >> num;
 	
    //첫 수자부터 입력 값까지 전부 탐색
	for (int i = 1; i < num; ++i) {
		sum = i; //분해합엔 본인이 들어가기에
		part = i; //자릿수들을 추출하기위해 다른 변수 사용
 
		while (part) { //각 자릿수를 더해준다.
			sum += part % 10; 
			part /= 10;
		}
 
		if (num == sum) { //상향 탐색임으로 처음나온 분해합 생성자가 제일 작은 생성자 
			cout << i << endl;
			return 0;
		}
	}
 
	cout << "0" << endl;
 
	return 0;
}