[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을 구현할 수 있다.

연산과정 횟수 일반화

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

풀이

	'''
	No: 1463
	Title: 1로 만들기
	Problem:
	정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
	- X가 3으로 나누어 떨어지면, 3으로 나눈다.
	- X가 2로 나누어 떨어지면, 2로 나눈다.
	- 1을 뺀다.
	정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
	Input:
	첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
	Output:
	첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
	Lang:
	Python 3
	Explanation:
	Memoization을 통하 Bottom-Up DP를 통해 시간복잡도를 줄인다
	'''
	X=int(input()) # 표준 입력 처리
	arr=[-1]*(X+3) # Memoization을 위한 리스트 선언 (IndexError를 피하기 위해 X+3 길이로 선언)
	arr[1]=0 # Bottom-Up DP를 위해 기본값 대입
	arr[2]=arr[3]=1
	if arr[X] == -1: # 연산 전 리스트에 이미 결과값이 존재한다면 연산을 수행하지 않는다.
	i=4 # index가 4이상이어야 리스트에 결과값이 존재하지 않기 때문에 i를 4부터 시작해도 된다.
	while i<X+1: # i를 4부터 X까지 1씩 증가시키며 하위 연산 수행
	tmp=[arr[i-1]] # 1을 빼는 경우
	if i%2==0:
	tmp.append(arr[int(i/2)]) # 2를 나누는 경우
	if i%3==0:
	tmp.append(arr[int(i/3)]) # 3을 나누는 경우
	arr[i]=min(tmp)+1 # 위 3가지 경우 중 최소값에 1을 더하여 arr[i]에 대입
	i+=1 # index 1 증가
	print(arr[X]) # 결과값 출력

view raw 1463.py hosted with ❤ by GitHub