217 Page 다이나믹 프로그래밍 문제 질문드립니다

[LeeWoojin-99]

안녕하세요 제가 217페이지의 다이나믹 프로그래밍 문제 '1로 만들기'를 풀어보았는데 저는 문제를 읽고 곰곰히 생각하여 탑다운 방식으로 문제를 풀어보았습니다. 문제를 풀고 답안을 보니 바텀업 방식으로 짜여진 코드인데 정말 정석적인 다이나믹 프로그래밍 이구나 싶어서 그 답안을 보니 제 코드는 뭔가 다이나믹 프로그래밍이 제대로 쓰여진 것 같지 않다고 느껴졌습니다. 그래서 탑다운 방식으로 코드를 짠다고 짰는데 왠지 이게 다이나믹 프로그래밍의 메모이제이션 기법이 사용된 게 맞나 햇갈려서 질문드립니다

'''
217 Page
1로 만들기

문제 설명
정수 X
정수 X에 사용할 수 있는 연산은 4가지
1. X가 5로 나누어 떨어지면 5로 나눈다.
2. X가 3... 동일
3. X가 2... 동일
4. X에서 1을 뺀다.
이렇게 4가지 연산을 이요항 1을 만들려고 한다.
연산을 사용하는 횟수의 최솟값을 구하시오.

입력 조건
첫째 줄 : 정수 X 입력

출력 조건
첫째 줄 : 연산을 사용하는 횟수의 최솟값 출력
'''
''' 문제 풀이
Top-Down 방식

1. 입력받은 값 x를 5로 나누었을 때 나머지 값이 0인지 검사한다.
2. 나머지 값이 0이라면 5로 나눈다. 그리고 1번 동작으로 돌아간다.
3. 나머지 값이 0을 초과한다면 -1을 한다.
4. -1을 한 값에 5로 나누었을 때의 나머지 값을 검사한다.
5. 0이라면 2-1번 동작으로 간다. 0을 초과한다면 3번 동작으로 간다.
6. 1~6에서 했던 동작들처럼 5로 나누는 것이 아닌 3으로 나누며 동작한다.
7. 6번처럼 숫자를 바꾼 것처럼 3으로 바꾼 것이 아닌 2로 바꿔서 동작한다.

1~7번 동작을 반복하며 1이 되는 횟수를 카운트한다.
'''
x = int(input())
arr = [5,3,2]
count = 0
def Divide532(x, n):
    global count
    if x%n == 0: #나머지가 0이라면
        count += 1
        return x//n #몫을 반환한다.
    else:
        x -= 1
        if x%n == 0:
            count += 2 #1을 빼는 연산, 나누는 연산. 총 연산을 두 번 하였으니 2를 더해준다.
            return x//n
        else:
            return x+1 #1을 뺀 값에서도 나누어지지 않을 경우 x에 +1을 해서 빼기 전의 값으로 되돌려준다.
while x != 1: #1이 되기 전까지 반복
    for i in arr: #5 3 2를 반복한다.
        After_x = Divide532(x, i) #함수를 거친 값을 After_x 변수에 담는다.
        if x != After_x: #값이 달라졌다면
            x = After_x #달라진 값으로 x를 갱신하고 for문을 나간다.
            break
        elif i == 2:
            #i==2 : 5와 3이 i값인 경우를 모두 거친 후인지 검사하기 위한 조건문
            #그냥 나누어도, 1을 빼고 나누어도 값이 나오지 않을 경우 x에서 1을 뺀 값으로 x를 갱신한다.
            x -= 1
print(count)