[Baekjoon 문제풀이] 1463 - 1로 만들기 (Python 3)

Baekjoon 문제풀이

서론

본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다.
대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다.

문제

Baekjoon 1463번 - 1로 만들기
https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

해법

Top-Down 방식의 재귀호출로 이 문제를 해결하려고 하면 시간초과로 막히게 될 것이다(사실 필자가 그랬다.)
사실 뭔가 재귀를 써야한다 싶으면 사실 Top-Down으로 풀어도 되는 문제는 없다... 그래서 아무튼 이번 문제는 Memoization을 통한 Bottom-Up DP를 사용해야 해결할 수 있다. 그전에 우선 이번 문제의 패턴을 파악해보겠다.

연산 과정

숫자 별 1이 되기 위한 연산 과정을 나열하보면 위와 같다. 여기서 눈치 챈 사람이 있을 수 있는데, 연산 과정 내에 중복되는 과정이 존재한다는 것이다. 중복이 있다는 것은 즉, 우리가 이 부분을 제거하면 더 효율적으로 결과를 얻어낼 수 있다는 것이다.

연산과정 패턴

위의 표에서 같은 색으로 연결해놓은 부분을 보면 패턴을 확인할 수 있다. 예외적으로 1이 되기 위한 연산 횟수 중 1은 0회, 2는 1회, 3은 1회가 필요하고 나머지 숫자들은 이전에 연산된 숫자와 중복되는 과정들을 지니고 있다. 따라서 숫자들마다의 필요 연산 횟수를 저장해두고 중복되는 연산이 발생할 시, 이를 수행하지 않고 저장된 값을 이용하여 Memoization을 구현할 수 있다.

연산과정 횟수 일반화

우리는 위와 같은 식을 얻을 수 있다. 이를 코드로 구현하면 된다.

풀이