[Programmers] 입문) 팩토리얼 (역추적)

 

처음 문제를 제대로 이해하지 못해 팩토리얼을 구하는 문제라고 읽었다.

알고보니 주어진 자연수 n이 가질 수 있는 가장 큰 팩토리얼 숫자를 찾는 것이 목표였다..

 

가장 우선적으로 팩토리얼 문제를 풀며 항상 사용했던 재귀함수와 팩토리얼을 반대로 찾아내는 함수를 생성하자

 

팩토리얼을 추적하기 위해는 3가지가 필요하다.

1. 목표 수

2. 현재 팩토리얼 결과 수

3. 현재 팩토리얼

 

solution(목표수){
	return 팩토리얼 (목표값, 현재 팩토리얼 결과 값, 팩토리얼값) 재귀
}
    
int 팩토리얼(목표값, 현재 팩토리얼 결과 값, 팩토리얼값){
	if (결과값이 목표값보다 큰가?)
        결과값이 더 높다면 이전 팩토리얼값를 반환
    
    팩토리얼 값 증가
    
    return 팩토리얼(목표값, 증가한 팩토리얼 값을 토대로 계산된 현재 팩토리얼 결과값, 증가한 팩토리얼값);
}

using System;

public class Solution {
    public int solution(int n) {
        return FactorialRewind(n);
    }
    
    private int FactorialRewind(int target, int number = 1, int counter = 1){
        if (target < number) return --counter;
        
         ++counter;
        
        return FactorialRewind(target, number * counter, counter);
    }
}