억억단을 외우자 [Lv. 3] (C++)

프로그래머스

1억 * 1억 크기의 곱하기 행렬이 있습니다.

( arr[0][2] * arr[2][0] = arr[2][2])

이때 행렬에서 모든 수가 몇번씩 나오는지 계산하고, 입력받은 starts에서 e까지 

가장 많이 나오는 수를 answer 배열에 담아 출력하면 되는 문제입니다.

 

풀이 방법

"행렬"이라는 키워드에 집중하면 더 복잡해집니다.

단순히 "특정 수를 만들기 위한 방법이 몇개인가?" 정도만 생각하여

1차원 배열에서 계산을 끝내야합니다.

 

가장 많이 고민하는 부분이 시간 초과일 것 입니다.

e * e번의 계산이 필요하다 생각할 수 있는데 두 수의 곱이 e를 넘으면 안되기 때문에

e Log e 정도의 계산으로 끝납니다

e == 100만일 때

100만 * 1 == 가능
50만  * 2 == 가능
25만  * 4 == 가능

100만과 50만 사이는 계산 없음
50만과 25만 사이도 계산 없음

 

e Log e의 속도로 계산이 끝났다면

starts 배열의 시작 index 부터 end 까지 가장 많이 나오는 수를 찾아야 합니다.

이는 정말 간단하게 해결이 가능합니다.

 

배열의 뒤에서 부터 탐색하여 가장 큰 수를 저장해나가면

e ~ 현재 index까지 가장 많이 나온 수를 저장할 수 있습니다.

 

이후 starts배열의 수를 인덱싱하여 answer 배열에 넣어 출력하면 해결됩니다.

 

정답 코드

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

using namespace std;

vector<int> solution(int e, vector<int> starts) {
    vector<int> dp(e+1), answer;
    
    for (int i = 1; i <= e; i++)
    {
        for (int j = 1; j <= e; j++)
        {
            if (i * j > e) 
                break;
            dp[i*j]++;
        }
    }
    
    int maxId = e;
    int maxV = dp[e];
    for (int i = e; i >= 0; i--)
    {
        if(dp[i] >= maxV)
        {
            maxId = i;
            maxV = dp[i];            
        }
        
        dp[i] = maxId;
    }
    
    for (int idx : starts)
        answer.push_back(dp[idx]);
  
    return answer;
}