백준 2057 - 팩토리얼 분해

https://www.acmicpc.net/problem/2057

2057번: 팩토리얼 분해

굉장히 많은 시간을 썼는데 풀지 못했다.

문제 설명도 부족한데 예제 입력도 하나만 딸랑 줘놓고 참나

다른 사람의 코드를 보고 간신히 이해했다.

 

맨 처음엔 이 문제가 입력된 숫자를 중복을 허용하고 팩토리얼들의 합으로 나타낼 수 있는지 없는지를 구하는 문제로 이해를 했다. 그래서 나온 코드는

import math

def find_result(n):
    i = 0
    print("i:", i)
    print("n", n)
    while True:
        fac = math.factorial(i)
        print("fac:", fac)
        if fac > n:  # 맞는 팩토리얼 존재 x
            return -1
        elif fac == n:  # 맞는 팩토리얼 존재
            if n == fac:
                return fac
        else:  # 적절한 팩토리얼이 나왔지만, 합까지는 도달하지 못 했을 때 => 계속해서 팩토리얼들을 찾아봐야함 ==> 합이 n과 같아질 떄 까지 ==> 안같아지면 -1 함수 종료
            print("팩토리얼 합 찾기 시작")
            n = n - fac
            while True:
                fac = find_result(n)
                n = n-fac
                if n == 0: # 팩토리얼의 합들이 존재할 때
                    return 1
            i += 1


n = int(input())
result = find_result(n)
if result == 1:
    print("YES")
else:
    print("NO")

재귀함수에 제일 약한 나인데 기껏 머리 터지도록 재귀함수 썼는데 틀렸다. 쩝,,

근데 생각해보면 중복을 허용해버리면 모든 수는 팩토리얼의 합으로 표현이 가능하다.

왜냐하면, 0!이나 1!은 1인데 1을 계속 더하면 그 수가 되겠지.. 

 

그래서 아 문제를 잘 못 이해하고 뻘짓했구나~하고 문제를 다시 보았다.

2 = 0! + 1! 이길래 주어진 숫자보다 작은 팩토리얼의 모든 합으로 표현할 수 있나 없나..하는 문제인줄

그래서 작성한 코드가

import math

n = int(input())
fac_num = []
i = 0

while True:
    num = math.factorial(i)
    if num <= n:
        fac_num.append(num)
        i += 1
    else:
        break
if n!=0:
    for i in range(len(fac_num)-1, -1, -1):
        n -= fac_num[i]
        if n == 0:
            print('YES')
            break

    if n!=0:
        print('NO')
else:
    print('NO')

이건데, 제출해보니까 자꾸 80%에서 오답처리가 되는 것이었다....

 

다른 사람의 정답 코드를 보니까 3을 입력했을 때 YES가 나오는데

이 코드는 3일 때 NO가 나온다.

문제 이해를 잘 못해서 3일 때 NO가 나오는게 맞는줄..

 

이 문제는 ㄹㅇ 해당 숫자가 서로 팩토리얼들의 합으로 표현될 수 있는지, 없는지 확인하는 문제이고(그대로 받아들일 것).. 이 문제를 풀려면 다음과 같은 로직이 필요하다.

 

1. 해당 숫자와 가장 가까운 값을 갖는 팩토리얼부터 차례대로 빼볼 것 

2. 뺀 숫자의 팩토리얼 리스트를 다시 구하기 단, 이미 사용된 팩토리얼은 사용이 불가능하므로 pop할 것

3. 뺀 숫자에 1~2의 과정을 다시 반복

 

이 1~3 로직을 반영하여 작성한 코드는 다음과 같다.

import math

n = int(input())
fac_num = []
i = 0

while True:  # 맨 처음 숫자에 올 수 있는 팩토리얼 리스트 구하기 => 어차피 그 다음 숫자의 팩토리얼 리스트는 해당 리스트보다 작으므로
    num = math.factorial(i)
    if num <= n:
        fac_num.append(num)
    else:
        break
    i += 1
if n==0:  # 0이 입력될 경우, 로직을 돌려볼 필요도 없이 NO
    print('NO')
else:
    if n in fac_num:  # 해당 숫자가 팩토리얼 수 그 자체일 경우, 로직을 돌려볼 필요도 없이 YES
        print("YES")
    else:
        while n>=0:  # 해당 숫자가 0이상일 때만 로직 실행
            fac_num =list(filter(lambda x: x<=n, fac_num))  # 해당 숫자의 팩토리얼 리스트(해당 숫자보다 큰 팩토리얼 숫자는 올 수 없음)
            if n in fac_num:  # 해당 숫자가 팩토리얼 그 자체일 경우, YES
                print('YES')
                break
            if len(fac_num) !=0:  # 해당 숫자가 팩토리얼 리스트를 갖을 경우
                n -= fac_num.pop()  # 해당 숫자에 가장 가까운 팩토리얼 수를 뺄 것(로직1) and pop을 시켜줘야 해당 리스트에서 제거되므로 중복을 방지할 수 있음
                if n==0:  # 뺀 결과가 0일 경우 ==> 합으로 표현이 가능하다는 의미
                    print('YES')
                    break
            else:  # 해당 숫자가 리스트를 안갖을 경우
                print('NO')  # 팩토리얼들의 합으로 나타낼 수 없음
                break

위에 보면 조건문들이 꽤 있는데 이건 그냥 시간 단축을 위해서 썼는데 별반 차이 없을 것 같다. 

어차피 pop()해서 접근하므로 해당 숫자가 팩토리얼일 경우, 바로 pop이 되므로 n=0이 바로 된다.

 

ex) 27 => YES

1. 27의 팩토리얼 리스트 : [1, 1, 2, 6, 24]

2. 27-24 = 3

3. 3의 팩토리얼 리스트: [1, 1, 2]

4. 3 - 2 = 1

5. 1의 팩토리얼 리스트: [1, 1]

6. 1 - 1 = 0 ==> YES!

 

ex) 19 => NO

1. 19의 팩토리얼 리스트: [1, 1, 2, 6]

2. 19 - 6 = 13

3. 13의 팩토리얼 리스트: [1, 1, 2]

4. 13 - 2 = 11

5. 7의 팩토리얼 리스트: [1, 1]

6. 7 - 1 = 6

7. 6의 팩토리얼 리스트: [] ==> NO!

 

스읍 이거 로직 생각을 못 해내겠음 .. 오늘 하루를 날렸네ㅋ

이해는 되는데 다시 풀라고 하라믄 못 풀겠다리..주륵