[C++] 프로그래머스 억억단을 외우자

https://school.programmers.co.kr/learn/courses/30/lessons/138475

프로그래머스

풀이

e의 범위와 start의 범위가 크기 때문에 DP를 사용해서 시간을 단축해야 하는 문제였다.

처음 구현한 건, i의 sheet변수가 0이라면 약수의 개수를 세어서 sheet 변수에 추가하고 *2 위치를 채워주는 것이었다. 이렇게 구현했을 때 10번 테스트 케이스에서 시간 초과가 난다.

2번째는 다른 분의 풀이를 참고했다. i에서부터 시작해서 e까지의 모든 i 배수를 채워주는 방식이다. 

이렇게 했을 때, e=15이면 sheet를 채우는데 걸리는 반복 횟수는 30번이고, 기존 방식은 42번(조건문 없을 때)으로 차이가 나게 된다. 조건문이 있다고 하더라도 e가 5,000,000이면 전자의 방식이 더 빠를 것이다.

테스트 결과 테스트 케이스 9번 결과에서 후자가 30배 이상 빨랐다.

답을 찾는 과정도 뒤에서부터 탐색을 시작해 현재 인덱스의 sheet 값이 max보다 크거나 같다면 인덱스와 max를 바꿔주는 방식으로 for loop 한번으로 끝낼 수 있다. 이렇게 하면 start 변수로 s 변수 인덱스에 바로 접근 하면 된다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int e, vector<int> starts) {
    ios::sync_with_stdio(false);
    vector<int> answer;
    vector<int> sheet(e+1, 0);
    for (int i = 1; i <= e; i++) {
        sheet[i]++;
    }
    //2부터 e까지의 숫자에 대한 약수 정보 삽입
    for (int i = 2; i <= e; i++) {
        for (int k = 1; k <= e/i; k++) {
            sheet[i * k]++;
        }
    }
    // 시간초과 코드
    // for (int i=1; i<=e; i++){
    //     int cnt=0;
    //     if (sheet[i]==0){
    //         for (int j=1; j*j<=i; j++){
    //             if (i%j==0){
    //                 if (i/j!=j) cnt+=2;
    //                 else cnt+=1;
    //             }
    //         }
    //         sheet[i]=cnt;
    //     }
    //     else{
    //         if (i*2<=e) {
    //             sheet[i*2]=sheet[i]+1;
    //         }
    //     }
    // }
    
    vector<int> s(e+1, 0);
    int max=0, idx=0;
    for (int i=e; i>0; i--){
        if (sheet[i]>=max){
            max = sheet[i];
            idx=i;
        }
        s[i]=idx;
    }
    
    for (int i=0; i<starts.size(); i++){
        answer.push_back(s[starts[i]]);
    }

    return answer;
}

실패코드