1로 만들기

1. 문제 정의

정수 X가 주어질 때, 4가지 연산이 주어진다.

 

- X가 5로 나누어 떨어질 때, 5로 나눈다.

- X가 3로 나누어 떨어질 때, 3로 나눈다.

- X가 2로 나누어 떨어질 때, 2로 나눈다.

- X에서 1을 뺀다.

 

예를 들면, 26이 주어지면 연산은 다음과 같이 계산되고, 이 경우 최소 횟수는 3이다.

 

- 26 -1  = 25

- 25 / 5 = 5

- 5 / 5 = 1

 

이 때, 연산을 사용하는 횟수의 최솟값을 구하시오.

 

 

2. 문제 해결

숫자를 주고, 1이 될 때 까지 연산을 계속 돌리는 그리디 문제로 보이지만, 어느 정수든 계산 중간의 결과가 같게 나온다.

예를 들어보면 125를 주면 계산 최소 횟수는 4로, 다음과 같다.

 

- 125 / 5 = 25

- 25 / 5 = 5 

- 5 / 5 = 1

 

연산 4가지를 수행하는 것을 통째로 f(x)라고 생각하면, f(25), f(5)는 반복되어 수행지는 것을 확인 가능하다. 즉, 함수가 반복적으로 호출된다.

 

DP 조건이 완성되었다. 큰 문제(정수)는 작은 문제(작은 정수)로 나눌수 있고, 작은 문제(작은 정수)의 결과는 큰 문제(큰 정수)에서도 동일하다. 그래서 한 번 해결한 문제는 그걸 저장하였다가 다른 답을 구할 때 이용할 수 있도록 한다.

 

그럼 이 이전의 결과는 어떻게 저장할까? list로 정답 리스트를 생성, 이를 이용해 작은 문제부터 순차적으로 얻어가는 bottom-up 방식을 사용하자. 사실 top-down 방식은 재귀를 이용하는데, 재귀 스택이 터질 위험이 있으므로 이 방식을 사용하는 게 더 안전하다.

 

바로 코드를 보면 다음과 같다.

작은 문제부터 얻으므로, 작게 갱신되는 연산부터 먼저 수행 여부를 검증한다. ( 코드에서 입력값은 1 이상 30000 이하 정수 )

 

2 에서 n 까지의 정수 범위에 대하여 각각 결과 리스트인 d에 연산 횟수를 기록하게 된다. 우선 1은 연산이 1번( -1 )이 수행된다.

 

2 이상 n 이하 정수 범위에 대해, 임의의 정수 x가 주어질 때 먼저 -1 연산은 언제나 가능하므로 수행함을 알린다. ( d[x] +1 갱신 )

그런다음 해당 x가 2,3,5로 나누어 떨어질 경우, x // 2 ( or 3, 5 )에서 각각 2,3,5가 곱해진 경우 ( 연산 1번 )를 의미한다.

그러므로 d[ x // 2 ( or 3, 5 ) ] + 1 ( 연산 1번 ), x를 해당 2,3,5로 나눈 값의 연산 횟수에 1을 더한 게 x의 연산 횟수가 된다.

 

이때, -1을 연산한 연산 횟수 ( d[x] )와 2,3,5 중 하나로 나누어 떨어질 경우, 나눗셈을 연산한 연산 횟수 ( d[ x // 2 ( or 3, 5 ) ] + 1 ) 중 작은 연산 횟수를 구하면 된다.

3. 느낀 점

내가 공부한 문제 유형 중 가장 이해하기 어려웠다. 코드야 이해하면 정말 쉽게 구현할 수 있지만, 문제를 이해하고 이를 제한 시간 안에 코드로 구현하기가 너무 어려웠다.

 

내가 이해한, DP의 해결 과정은 다음과 같다.

 

- 1. 해당 문제가 DP를 사용하여 해결할 수 있는가? ( DP의 조건을 만족하는가?, 시간 또는 메모리가 매우 제한적인가? )

- 2. 그림 등을 활용해 규칙을 찾아서, 점화식을 얻을 수 있는가? ( 단순히 점화식 뿐만 아니라, 최대 & 최소 => min, max 함수로 이용 가능 )

- 3. bottom - up & top - down 중 결정 ( 대부분 bottom - up, 그러므로 결과 리스트인 d = [초깃값] * ( 조건 ) 선언 )

- 4. 점화식을 코드로 구현

 

하지만, 1번으로 해결 가능한 지 검증을 해보아야 하고, ( 그리디 또는 분할 정복 등의 유형과 비슷하기 때문에 )

점화식을 구할 수 있는지가 관건이다. 처음 유형을 공부해보면 코드야 쉽지 어디서 부터 아이디어를 얻는지부터 난감할 것이다.

 

그래도 다양한 유형을 연습하고, 문제를 접할 때 DP와 연결이 될 수 있는지 계속 신경쓰면서 알고리즘을 생각해보면 대강 감이 잡힐 것이라 생각한다. ( 나도 공부 중이라 어떻게 구현할 지 매우 막막한 경우가 많다. )