[프로그래머스/C++] 숫자 블록

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 규칙에 따라 블록을 채우면 되는 문제다.

 

규칙을 잘 보면 k번째 블록이 임의의 수 n으로 나누어지는지 판단하면 되는 문제기 때문에 k번째 블록의 약수를 구하는 문제로 볼 수 있다.

 

여기서 k번째 블록의 약수를 구하기 위해서 1~k까지 계산할 필요가 없다.

 

왜냐하면 k번째 블록의 약수를 k = a * b로 표현할 수 있는데, 이 때 a<b 라면 b로 k를 나누지 않아도 k/a=b 를 이용해 b가 약수임을 알 수 있기 때문이다.

 

그러므로 임의의 두 수를 곱해서 k를 만드는 약수를 구하기 위해서는 1~sqrt(k)까지만 계산하면 된다.

(sqrt(k)~k사이에 있는 약수는 1~sqrt(k)와 곱해서 k를 만들게 되므로 계산할 필요가 없다.)

 

문제에서는 k번째 위치에 k번 블록을 쌓을 수 없으므로 자기자신을 제외한 약수 중에서 가장 큰 약수가 k번째 자리에 오게 된다.

 

그러므로 약수를 구하는 방법을 이용해 계산하면 최악의 경우 5000*sqrt(n)으로 문제를 해결할 수 있다.

 

 

​

[아이디어 정리]

1. 자기자신을 제외한 약수 중 가장 큰 값을 구한다. (여기서 쌓을 수 있는 블록의 가장 큰 번호는 10,000,000 이다.)
2. 약수를 구할 때, 2~sqrt(k)까지만 계산해도 sqrt(k)~k범위에 있는 약수를 구할 수 있음을 이용해 시간을 줄인다.
3. 구한 번호들을 return 한다.

 

 

Code

 

 

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

int Calc(int n)
{
    int retAns=1;
    if (n<=1)
    {
        return 0;
    }
    else if (n<=2){
        return 1;
    }
    for (int i=2; i<=pow(n,0.5)+1; i++)
    {
        if (n%i==0)
        {
            retAns=i;
            if (n/i<=10000000)
            {
                retAns=n/i; // 이 if문에 처음 들어오면 10000000 이하의 약수 중 가장 큰 수다.
                break;
            }
        }
    }
    return retAns;
    
}
vector<int> solution(long long begin, long long end) {
    vector<int> answer;
    for (int i=begin; i<=end; i++)
    {
        answer.push_back(Calc(i));
    }
    return answer;
}

 

---

처음에 제한사항에 블럭의 범위가 없어서 블럭의 범위가 1,000,000,000 인 줄 알고 문제를 풀었다.

알고보니 문제에 블럭의 범위는 10,000,000이라고 정해져 있었다;;

프로그래머스