[BOJ] 1463번 1로 만들기 / 사용언어 : 파이썬(python)

※ 문제링크

1463번: 1로 만들기

※ 관련개념

메모이제이션 - 위키백과, 우리 모두의 백과사전

해당 문제는 메모이제이션을 활용하여 각각의 계산결과를 저장하고 그 이후 계산을 이전 리스트를 참조해서 풀어야 하는 문제였다. 문제해결 코드를 작성하는 것은 크게 어렵지 않았으며, 자세한 문제풀이방법과 코드는 아래와 같다.

1. 처음 받은 입력값을 2차원 리스트 형태로 저장한다.

2. 3가지 연산을 모두 진행하고 그 리스트를 dp리스트에 추가한다.

3. 추가할 리스트에 1이 있는 경우 반복문을 중지하고 실행한 반복횟수를 출력한다.

 

N = int(input())
dp = [[N]]
cnt = 0
while 1 not in dp[cnt]:
    dp_next = []
    for dp_past in dp[cnt]:
        dp_next.append(dp_past - 1)
        if dp_past % 3 == 0:
            dp_next.append(dp_past // 3)
        if dp_past % 2 == 0:
            dp_next.append(dp_past // 2)
    dp.append(dp_next)
    cnt += 1
print(cnt)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.