[알고리즘 연습] 주어진 숫자를 1로 만들기 위한 최소 횟수 구하기

주어진 숫자를 1로 만들기 위한 최소 횟수 구하기

• int형의 숫자 num이 주어졌을 때 해당 num을 한정된 연산을 이용해 최대한 적은 연산 횟수로 1을 만들어야 한다. 가장 적은 케이스의 횟수를 구하라.
• 할 수 있는 연산은 3으로 나누기, 2로 나누기, 1 빼기 총 세가지이다.

---

풀이

def convertTo1(num):
    now = 1
    tries = 0
    check = [0 for _ in range(1,num + 1)]

    for i in range(0,num):
        tries = check[i]

        now_num = i + 1

        plus_one_index = now_num + 1 - 1
        mul_two_index = now_num * 2 - 1
        mul_three_index = now_num * 3 - 1

        if (plus_one_index) < num:
            if (check[plus_one_index] == 0) or (check[plus_one_index] > (tries + 1)):
                check[plus_one_index] = tries + 1

        if (mul_two_index) < num:
            if (check[mul_two_index] == 0) or (check[mul_two_index] > (tries + 1)):
                check[mul_two_index] = tries + 1

        if (mul_three_index) < num:
            if (check[mul_three_index] == 0) or (check[mul_three_index] > (tries + 1)):
                check[mul_three_index] = tries + 1

    return check[-1]

• 거꾸로 1부터 시작하여 곱하고 더해 특정 수에 접근하는 방법을 생각해보았다.
• 리스트로 구성한 뒤 for문을 한번 돌면서 리스트의 값들을 갱신하는 방식으로 구성했다. 각 리스트의 값은 리스트의 인덱스번호+1에 해당하는 수의 최소 연산횟수를 뜻한다.
• 처음엔 전부 0으로 초기화하고, 1(인덱스 0)부터 시작해서 리스트에 해당하는 값이 0이거나, 현 연산횟수+1보다 클 경우 새로 갱신한다.
• 처음에 인덱스가 0일 경우를 제대로 고려하지 않아서 알고리즘이 자꾸 꼬여서, 아예 인덱스 접근시 사용할 변수를 따로 설정했다. (실제숫자에 연산을 수행한 값) - 1이 각각의 인덱스이다.