[Python] 2057번 팩토리얼 분해

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

2057번: 팩토리얼 분해

---

 

22/09/15

 

 

같은 그룹원에게 추천받아서 풀었던 그리디 문제인데, (그리디인 줄 모르고 풀었었다) 접근방법을 틀리게 할 때가 많았던 문제이다.

 

역시 그리디는 그리디인줄 모르고 풀어야 그 진정한 어려움을 알 수 있다고 했던가, 정말 힘들었다.

 

이후에 브루트 포스로 풀 수 있다는 것을 깨닫고, 조금 허탈함을 느끼긴 했다.

---

 

문제 접근 방식:

 

 

맨 처음에 접근 할 때 잘 모르겠어서 그룹원의 힌트를 보고 접근했다.

 

그 그룹원 분은 1!부터 n! 까지의 합이 n+1! 보다 작다는 점을 힌트로 주었다.

 

힌트를 얻고 문제 접근 방식을 다음과 같이 하였다.

 

N에서 0!, 1!, 2!... 을 차근차근 빼다가 음수가 나오면 실패, 0이 나오면 성공이겠구나,라고 생각을 잘못했었다.

---

아래는 내가 위의 접근 방식과 같이 작성한 잘못된 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2057번 팩토리얼 분해
# 수학, 그리디
'''
접근 방법:
앞에 있는 팩토리얼들을 모두 더해도 그 다음 팩토리얼 숫자가 나오지 않기 때문에
그냥 N에서 0!, 1!, ... 차근차근 빼다가 음수가 나오면 실패,
0이 나오면 성공
'''
from math import factorial
N = int(input())
k = 0
while True:
    if N == 0:
        print('YES')
        break
    elif N < 0:
        print('NO')
        break
    N -= factorial(k)
    k += 1

 

---

 

근데 알고보니, 1! + 2! + 8! 과 같은 반례들이 있다는 것을 보고 이 접근 방식은 틀렸다는 사실을 알게 되었다.

 

이 반례를 통해 그렇다면, N이 주어질때, N보다 작거나 같은 최대의 k! 을 빼도록 하자,라고 생각했다.

 

결론만 이야기 하자면, 접근 방법 자체는 맞았으나, 한 가지 빼먹고 구현한 것이 있어서 틀렸습니다를 많이 받았다.

 

바로 0!과 1! 의 유무, 그리고 k! 을 이미 사용했더라면, 체크를 해줌으로써 다시 못 빼도록 하는 것이었다.

 

0! 과 1! 은 두 개가 같기 때문에 N보다 작거나 같은 최대의 k! 을 뺄 때 자칫 잘못하면 여러 번 빼거나 한 번만 빼도록 코드가 구현될 수 있다.

 

이런 부분들 때문에 많이 틀렸고, 결국 최종적으로 맞은 코드는 다음과 같다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2057번 팩토리얼 분해
# 수학, 그리디
'''
접근 방법:
앞에 있는 팩토리얼들을 모두 더해도 그 다음 팩토리얼 숫자가 나오지 않기 때문에
그냥 N에서 N이랑 가까운 팩토리얼을 차근차근 빼다가 음수가 나오면 실패,
0이 나오면 성공
'''
from math import factorial
N = int(input())
check = [0 for _ in range(21)]
check[20] = 1
k = 19
fac = factorial(19)
if N != 0:
    while True:
        while True:
            k = check.index(1) - 1
            fac = factorial(k)
            check[k] = 1
            if N >= fac:
                break
        N -= fac
        if check[0] == 1 or N == 0:
            break
    if N == 0:
        print('YES')
    else:
        print('NO')
else:
    print('NO')