[C++]프로젝트 오일러 12번 문제&풀이 (500개 이상의 약수를 갖는 가장 작은 삼각수는?)

문제

1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다.
예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 됩니다.
이런 식으로 삼각수를 구해 나가면 다음과 같습니다.

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

이 삼각수들의 약수를 구해 봅시다.

 1: 1
 3: 1, 3
 6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28

위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다.

그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까?

 

 

접근방법(1차) - 코드는 맨 밑에!

1. 삼각수를 차례로 1부터 해당 숫자까지로 일일히 나누어 본다.

  (3이면 1,2,3으로 나누고, 6이면 1,2,3,4,5,6으로 나누고)

2. 이렇게 나누어 떨어지는 수, 즉 약수가 500개 이상이면 반복문을 종료한다.

→ 코드는 간단하지만, 시간이 너무 오래 걸린다ㅠㅠ

개선사항

1. 1부터 해당 수까지의 모든 숫자로 나눠봐야 하므로 연산량이 많다.

2. 소인수 분해를 통해 각 소인수의 지수에 1을 더해서 곱하는 방식으로 프로그램 변경!

 

9분 53초 소요

약수의 개수 참고 링크

namu.wiki/w/%EC%95%BD%EC%88%98(%EC%88%98%ED%95%99)

약수(수학) - 나무위키

접근방법(2차) - 코드는 맨 밑에!

1. 삼각수를 차례로 소인수 분해를 한다.

2. 소인수 분해를 하기 위해 소인수들을 차례로 벡터(div_vec)에 넣는다.

3. 소인수가 들어있는 벡터(div_vec)에서 지수만 산출하여 다른 벡터(cnt_vec)에 넣는다.

4. 이렇게 소인수의 지수가 들어있는 벡터(cnt_vec)를 이용하여 약수의 개수를 구한다.

→ 접근 방법은 맞는거 같으나, 시간이 더 오래 걸린다ㅠㅠ

개선사항

1. 소인수가 들어있는 벡터(div_vec)에서 지수만 산출할 때, 2부터 해당 숫자까지 1개씩 증가시키며 해당 되는 소인수의 지수를 구하므로 연산량이 많다.

2. 소인수만 담겨있는 벡터를 이용하여 연산량을 줄이는 방법으로 개선!

20분 1초

접근방법(3차)

1. 접근방법(2차)에서 소인수의 지수의 개수를 구하는 알고리즘 변경

→ 120의 경우 소인수가 들어있는 벡터(div_vec)에 2 2 2 3 5 이와 같이 담기는데, 접근방법(2차)에서는 1부터 120까지 하나하나 개수를 다 세어봤었다면, 접근방법(3차)에서는 5개의 공간에서만 개수를 세는 방식으로 변경하였다.

1초 컷!

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n = 1;
    int num = 0;
    int count_con = 0;

    while (true)
    {
        vector<int> div_vec;
        div_vec.clear();
        num += n;
        int num_copy = num;
        int count_ = 1;

        if (num == 1)
        {
            count_ = 1;
            //cout << num << " : \t" << count_ << endl;
        }

        else
        {
            int i = 2;

            while (i <= num_copy)
            {
                if (num_copy == 1)
                    break;
                if (num_copy % i != 0)
                    i++;
                else
                {
                    div_vec.push_back(i);
                    num_copy /= i;
                }
            }

            // check_1
            /*for (int m = 0; m < div_vec.size(); m++)
            {
                cout << div_vec[m] << " ";
            }
            cout << endl;*/

            int j = 0;

            vector<int> cnt_vec;
            cnt_vec.clear();

            while (j < div_vec.size())
            {
                int cnt = 0;
                cnt = count(div_vec.begin(), div_vec.end(), div_vec[j]);
                if (div_vec[j] != div_vec[j+1])
                {
                    cnt_vec.push_back(cnt);
                }
                j++;
            }

            // check_2
            /*for (int m = 0; m < cnt_vec.size(); m++)
            {
                cout << cnt_vec[m] << " ";
            }
            cout << endl;*/

            for (int k = 0; k < cnt_vec.size(); k++)
            {
                count_ *= (cnt_vec[k] + 1);
            }

            //cout << num << " : \t" << count_ << endl;
        }
        count_con = count_;

        if (count_ >= 500)
            break;

        n++;
    }
    cout << "Answer is : " << num << " / " << count_con << endl;

    return 0;
}

 

접근방법(1차) 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n = 1;
    int num = 0;
    int count = 0;

    while (true)
    {
        num += n;

        for (int i = 1; i <= num; i++)
        {
            if (num % i == 0)
                count++;
        }

       // cout << num << " : \t" << count << endl;

        if (count >= 500)
            break;
        else
            count = 0;

        n++;
    }

    cout << "Answer is : "<< num << " / " << count << endl;
    
    return 0;
}

 

접근방법(2차) 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n = 1;
    int num = 0;
    int count_con = 0;
    
    while (true)
    {
        vector<int> div_vec;
        div_vec.clear();
        num += n;
        int num_copy = num;
        int count_ = 1;
        
        if (num == 1)
        {
            count_ = 1;
            cout << num << " : \t" << count_ << endl;
        }

        else
        {
            int i = 2;

            while (i <= num_copy)
            {
                if (num_copy == 1)
                    break;
                if (num_copy % i != 0)
                    i++;
                else
                {
                    div_vec.push_back(i);
                    num_copy /= i; 
                }
            }

            int j = 2;
            
            vector<int> cnt_vec;
            cnt_vec.clear();

            while (j <= num)
            {
                int cnt = 0;
                cnt = count(div_vec.begin(), div_vec.end(), j);
                if (cnt != 0)
                {
                    cnt_vec.push_back(cnt);
                }
                j++;
            }

            for (int k = 0; k < cnt_vec.size(); k++)
            {
                count_ *= (cnt_vec[k] + 1);
            }
            
            cout << num << " : \t" << count_ << endl;
        }
        
        count_con = count_;

        if (count_ >= 100)
            break;

        n++;
    }

    cout << "Answer is : " << num << " / " << count_con << endl;

    return 0;
}

 

참고

https://github.com/mannlim/ProjectEuler

mannlim/ProjectEuler