탐욕적으로 생각하기 연습 -팩토리얼 분해-

1. 문제

 

2057번: 팩토리얼 분해 (acmicpc.net)

2057번: 팩토리얼 분해

 

주어진 정수가 여러개의 팩토리얼의 합으로 나뉠 수 있는지 검사하는 문제

 

2. 풀이1

 

실버 5인데 왤케 어렵냐...

 

그리디 알고리즘이 확실히 경험이 없긴한가봐

 

내 해법은 일단.. 어떤 정수 N을 팩토리얼로 분해한다고 하면... 당연히 팩토리얼 값은 N보다 작아야 할 것이다

 

그래서 N보다 작은 팩토리얼을 일단 모두 구해놓는다

 

from sys import stdin

n = int(stdin.readline())

i = 1

fact_list = [1]

factorial = 1

while 1:
    
    factorial *= i

    if factorial > n:
        
        i -= 1
        
        break

    fact_list.append(factorial)

    i += 1

 

 

그러면 팩토리얼을 모아놓은 fact_list에는 작은 팩토리얼 0!부터 큰 팩토리얼까지 오름차순으로 정렬되어 있을 것이다.

 

그래서 n에 큰 팩토리얼부터 빼본다

 

만약에 빼다가 0이 되면 바로 break하고 YES라고 하면 될 것이고

 

음수나 양수가 될 수 있는데 음수라고 해서 바로 탈출해야할까?

 

yes = False

while 1:
    
    res = n

    start = i

    for j in range(start,-1,-1):
        
        res -= fact_list[j]
        
        if res == 0:
            
            yes = True
            break

 

근데 이게 음수가 된다고 바로 탈출하면 안되는게

 

예를 들어 N = 26이면 팩토리얼을 4! = 24까지 구해놓을 것이다

 

[1,1,2,6,24]

 

그럴때, 26에서 24를 빼보고, 다음에 6을 빼면, 음수가 되는데

 

음수가 되니까 NO라고 해버리면

 

사실 26 = 24 + 2 = 4! + 2!로 분해가 되는데 안된다고 하는 것이다

 

그러니까 빼다가 음수가 되면 다시 복구를 해서 다음 수를 빼본다

 

while 1:
    
    res = n

    start = i

    for j in range(start,-1,-1):
        
        res -= fact_list[j]

        if res < 0:
            
            res += fact_list[j]
        
        elif res == 0:
            
            yes = True
            break

 

근데 이제 그러다가 0이 안될 수 있단 말이지

 

그러면 start가 fact_list의 끝번호부터 시작하는데.. 끝번호 -1부터 다시 검사해보도록 하자 이거지

 

반복문을 돌다가 yes가 True가 되면, 당연히 분해 할수 있다는 뜻이고

 

계속 검사했는데 i = -1이 되어버리면 아무리해도 못한다는 뜻이므로 탈출하고 NO라고 출력

 

yes = False

while 1:
    
    res = n

    start = i

    for j in range(start,-1,-1):
        
        res -= fact_list[j]

        if res < 0:
            
            res += fact_list[j]
        
        elif res == 0:
            
            yes = True
            break
    
    i -= 1
    
    if i == -1:
        
        break
    
    if yes == True:
        break

if yes:
    
    print('YES')

else:
    
    print('NO')

 

3. 풀이2

 

조금 더 깔끔한 풀이는

 

-------------------------------------------------------------------------------------------------------------------------------------------------------

 

모든 음이 아닌 정수 n에 대하여, $$0! + 1! + ... + (n-1)! <= n!$$을 만족한다.

 

구체적으로 생각해보면

 

n = 0이면 0! = 0!

 

n = 1이면 0! = 1!

 

n = 2이면 0! + 1! = 2!

 

n = 3이면 0! + 1! + 2! < 3!

 

n = 4이면 0! + 1! + 2! + 3! < 4!

 

n = 5이면 0! + 1! + 2! + 3! + 4! < 5!

 

...

 

결국 n >= 3이면, $n! > 0! + 1! + ... +(n-1)!$

 

n < 3이면, $n! = 0! + 1! + ... + (n-1)!$

 

어떤 정수 N에 대해 N보다 작은 모든 팩토리얼을 구해서 [0!, 1!, ... , k!]까지 구할 것이다

 

만약에 $k! <= N < (k+1)!$이 성립하는 정수 k가 있다고 하자.

 

그러면 $$0! + 1! + ... +(k-1)! <= k! <= N < (k+1)!$$

 

그러므로, $k! - (0! + 1! + ... + (k-1)!) >= 0$

 

여기서 위에 보인 것처럼 k >= 3이면, $k! - (0! + 1! + ... + (k-1)!) > 0$이다.

 

이 부등식이 무엇을 의미하는가?

 

N보다 작은 k!에 모든 0!, 1!, ... ,(k-1)!을 빼더라도, 반드시 0보다 큰 수가 남는다는 뜻이다.

 

그러면 당연히, N에 모든 (k-1)! , ... 0!을 빼더라도 반드시 0보다 큰 수가 남는다는 뜻이다.

 

while 1:
    
    res = n

    start = i

    for j in range(start,-1,-1):
        
        res -= fact_list[j]

        if res < 0:
            
            res += fact_list[j]
        
        elif res == 0:
            
            yes = True
            break
    
    i -= 1
    
    if i == -1:
        
        break
    
    if yes == True:
        break

 

그래서 내가 이렇게 [0!, 1!, ..., k!]까지 구했을때,

 

n에서 k!, ..., 0!까지 빼보면서 0이 안되면,

 

(k-1)!, ..., 0!까지 빼보면서 0이 안되면...

 

....

 

1!, 0!까지 빼보면서 0이 안되면..

 

0!빼보면서 0이 안되면...

 

이렇게 했잖아

 

근데 

 

"""

(k-1)!, ..., 0!까지 빼보면서 0이 안되면...

 

....

 

1!, 0!까지 빼보면서 0이 안되면..

 

0!빼보면서 0이 안되면...

"""

 

이 부분이 그냥 의미 없는 행동이다 이 뜻이라는 거지

 

그냥 "n에서 k!, ..., 0!까지 빼보면서 0이 안되면," 이것만 해도 답이 나온다 이 뜻이다

 

---------------------------------------------------------------------------------------------------------------------------------

 

따라서 n보다 작은 팩토리얼을 모두 구해놓고

 

그러한 팩토리얼을 모아놓은 리스트를 큰 수부터 순회를 해서

 

현재 순간에 n이 팩토리얼보다 크거나 같다면, n에서 빼주고

 

그렇지 않다면 그냥 넘기는 것이다

 

모든 팩토리얼을 돌았을때, 0이 된다면 분해할 수 있다는 뜻이고, 그렇지 않다면 분해할 수 없다는 뜻이다

 

그런데 예외가 있었지

 

n = 2이면 어떨까

 

[0!, 1!, 2!]까지 구하고 n >= 2!이므로, n - 2! = 0이니까, yes

 

n = 1이면..

 

[0!, 1!]까지 구하고, n >= 1!이므로, n - 1! = 0이니까, yes

 

따라서, 예외 케이스도 상관없다

 

from sys import stdin

n = int(stdin.readline())

#n이 0이면 바로 NO를 출력
#어떻게 다르게 할 수 있을것 같기는 한데..
if n == 0:
    
    print('NO')

else:

    i = 1

    fact_list = [1]

    factorial = 1

    while 1:

        factorial *= i

        if factorial > n:

            i -= 1

            break

        i += 1

        fact_list.append(factorial)
    
    #팩토리얼 리스트를 큰 수부터 순회해서, 
    #순간순간 n이 팩토리얼보다 크거나 같다면, n에서 팩토리얼을 계속 빼준다
    for j in range(i,-1,-1):

        if n >= fact_list[j]:

            n -= fact_list[j]

    if n == 0:

        print('YES')

    else:

        print('NO')

 

 

물론 내가 처음 짠 코드에서도..

 

1번만 해도 통과함

 

from sys import stdin

n = int(stdin.readline())

i = 1

fact_list = [1]

factorial = 1

while 1:
    
    factorial *= i

    if factorial > n:
        
        i -= 1
        
        break

    fact_list.append(factorial)

    i += 1


yes = False
    
res = n

start = i

for j in range(i,-1,-1):

    res -= fact_list[j]

    if res < 0:

        res += fact_list[j]

    elif res == 0:

        yes = True
        break

if yes:
    
    print('YES')

else:
    
    print('NO')