C++:: 프로그래머스 < 억억단을 외우자 >

생각보다 간단한 문제인데 시간초과 때문에 애를 먹은 문제이다. 핵심적인 문제의 풀이는 해당 구간의 수들중 약수의 개수가 가장 큰 값(중복이면 작은 값)을 찾아주면 되는 문제이다. 이때 해당구간에서 v.begin() - max_element(v.begin()+s, v.begin()+e)를 사용하여 약수가 큰값찾아주면 시간초과가 나게되어서 dp를 사용하여 접근하였다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(int e, vector<int> starts)
{
    vector<int> answer, v(e+1, 1), dp(e+1, 0);
    int s = *min_element(starts.begin(), starts.end());//starts의 원소중 가장 작은값
    for(int i=2;i<=e;i++)// v[i]는 i의 약수의 개수 이다.
        for(int j=i;j<=e;j+=i) v[j]++;
    dp[e] = e;
    for(int i=e-1;i>=s;i--)
    {//중복되는 약수 최대값이면 값이 작은것으로 갱신해줘야해서 거꾸로 간다.
        if (v[i] >= v[dp[i+1]]) dp[i] = i;// i의 약수개수가 이전까지의 범위에서의 최대 약수의 개수보다 크거나 같다면 갱신
        else dp[i] = dp[i+1];// 아니라면 이전값 그대로 전달
    }
    for(auto s : starts) answer.push_back(dp[s]);
    return answer;
}