Lv 0. 팩토리얼

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

 

#include <string>
#include <vector>

using namespace std;

int d[11];

int solution(int n) {
    int answer = 0;
    d[1]=1;
    for(int i=2; i<=10;i++){
        d[i]=d[i-1]*i;
    }
    for(int i=1; i<=10; i++){
        if(n>=d[i]) answer=i;
    }
    return answer;
}

dp를 이용하여 문제를 풀었다. 먼저 1부터 10항까지 팩토리얼을 구해서 dp배열에 저장해두고, 해당 값들을 활용해서 n보다 작은 값중에 가장 가까운 값을 반복문을 통해 answer에 저장되도록 for문을 돌렸다. 

 

이때 처리속도를 가져와보면, 

테스트 1 〉	통과 (0.01ms, 4.21MB)
테스트 2 〉	통과 (0.01ms, 3.68MB)
테스트 3 〉	통과 (0.01ms, 3.59MB)
테스트 4 〉	통과 (0.01ms, 4.16MB)
테스트 5 〉	통과 (0.01ms, 4.2MB)
테스트 6 〉	통과 (0.01ms, 3.66MB)

이와같은 결과를 얻을 수 있었다. 

 

이 문제의 경우 다른 사람의 풀이를 보면, 가장 처음에 나와있는 풀이가 재귀를 이용해서 factorial 함수를 선언하고 내부적으로 지속적으로 factorial 함수의 차수를 낮추어서 불러들여서 연산을 진행하는 방식인데, 이런 형태의 코드를 가져와보면 아래와 같다. 

케이스가 작은 문제의 경우는 재귀를 통해서도 풀 수 있음을 기억하도록 하자. 

#include <string>
#include <vector>

using namespace std;
int factorial(int n)
{
    if(n == 0 || n == 1)
        return 1;
    else
        return n*factorial(n-1);
}
int solution(int n) {
    int i = 0;
    while(factorial(i) <= n)
        i++;
    i--;
    return i;
}