[백준/BOJ] #1463 1로 만들기.python(파이썬)

문제 링크 / 출처

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

1463번: 1로 만들기

 

풀이

3가지 연산방법을 적절히 사용해서 최소횟수로 주어진 수를 1로 만드는 문제이다.

 

최소 연산 횟수를 구하는 데에 규칙을 발견하지 못하여 모든 경우의 수를 계산하는 형태로 풀이하였다.

 

재귀함수로도 구현했는데, 입력하는 수에 따라 Recursion Error가 발생하여 폐기하였다.

 

코드

N = int(input())
cnt = 0
pre_list = [N]

if N == 1:  # N이 1일 경우 연산할 필요가 없으므로 0출력
    print(0)

else:       # 3가지 방법을 이용하는 경우의 수를 모두 탐색
    while True:

        cnt += 1
        now_list = []

        for num in pre_list:
            if num % 3 == 0:            # 1번 연산
                now_list.append(num // 3)

            if num % 2 == 0:            # 2번 연산
                now_list.append(num // 2)

            now_list.append(num - 1)    # 3번 연산

        if 1 in now_list: # 연산의 결과가 1이 되는 순간 while문 탈출
            break

        pre_list = list(set(now_list)) # 중복된 값을 제거

    print(cnt)