[파이썬]-백준(BOJ)12852 _ 1로만들기 ver 2

 

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

12852번: 1로 만들기 2

 

해설

정답을 위한 배열을 만들어 주고 

인덱스를 돌면서 1+, 2*, 3* 인덱스에 자기 연산 더하기 1을 저장해주는데 이미 들어가 있는 값보다 작을 경우에만 해준다.

그리고 경로배열은 점화식으로 저장해준다 

처음에 무식하게  윗줄부터 3 나누고 2나누고 1 빼서 구하려고했지만 불가능했다.

그다음 Deep Copy 를 이용해 경로들을 저장해 주었지만 소용이 없었다.

Deepcopy는 새로운배열을할당해 시간이 오래 걸리고 

얕은 복사를 하니 다른경로들도 다 저장되는 오류가 생겼다

 

# https://www.acmicpc.net/problem/12852
# 1로 만들기 버전 2
import copy
import sys
 
 
# dp로 만들어서 해결하기
 
 
#
# def solution(n):
#     answer1 = 1e9
#     answer2 = [0]
#     cnt = 0
#
#     while n != 1:
#         cnt += 1
#         if n % 3 == 0:
#             n //= 3
#         elif n % 2 == 0:
#             n //= 2
#         else:
#             n -= 1
#
#     # 1일때 그전 결과 값이랑 비교
#     if n == 1:
#         answer1 = min(answer1, cnt)
#         return answer1
 
def solution(n):
    answer = [100000000] * (10 ** 6 + 1)  # 그냥배열
    answer2 = [[1]] * (10 ** 6 + 1)  # 경로배열
    answer3 = []  # 더하기 만 하는 경로
    # 초기 3갯값 설정
    answer[1], answer[2], answer[3] = 0, 1, 1
    answer2[1], answer2[2], answer2[3] = [1], [1, 2], [1, 3]
    # 1,2,3이면 1 반환
    if 0 < n < 4:
        return answer[n], answer2[n]
 
    # 1부터 돌기
    for index in range(1, n):
        # 지금 꺼에 1을 더한게 더 작다면 ?
        if answer[index] + 1 < answer[index + 1]:
            answer[index + 1] = answer[index] + 1  # 작은값으로 대체
            # answer2[index + 1] = copy.deepcopy(answer2[index])  # 경로도 대체
            # answer2[index + 1].append(index + 1)  # 그 값 더해주기
            answer2[index + 1] = answer2[index] + [index + 1]
            # answer3.append(index)
        # 만약 3을 곱했을 때 n을 넘기지 않는다면
        if index <= (n // 3):
            if answer[index] + 1 < answer[index * 3]:
                answer[index * 3] = answer[index] + 1
                # answer2[index * 3] = copy.deepcopy(answer2[index])
                # answer2[index * 3].append(index * 3)
                # answer3.append(index)
                answer2[index * 3] = answer2[index] + [index * 3]
 
        # 만약 2를 곱했을 때 n을 넘기지 않는다면
        if index <= (n // 2):
            if answer[index] + 1 < answer[(index * 2)]:
                answer[index * 2] = answer[index] + 1
                # answer2[index * 2] = copy.deepcopy(answer2[index])
                # answer2[index * 2].append(index * 2)
                # answer3.append(index)
                answer2[index * 2] = answer2[index] + [index * 2]
 
    # print(answer3)
    return answer[n], answer2[n]
 
 
if __name__ == '__main__':
    answer = (solution(int(sys.stdin.readline())))
 
    print(answer[0])
    print(*answer[1][::-1])
 
# 3
# 10  9 3 1