[백준] 1463번: 1로 만들기

https://www.acmicpc.net/problem/1463

Initial approach

I defined dp[i] represents the minimum number of ways to represent number i via the 3 ways that question defined.

I then thought of edge cases like 6 that is divisible by both 2 and 3. I would be taking the min(dp[i//2],dp[i//3]) and adding 1 to it for dp[6]. Another edge case would be the odd or prime values like 11. We cannot divide it by 2 or 3 so we can only minus one. So we take the previous number (10) and its' dp value and add it by 1. (dp[11]=dp[10]+1)

My initial thought, however, didn't account for all the possible cases for numbers that are divisible by 2 or 3. I initially just took
dp[i] = dp[i//2] +1 but there is another way to reach number i other than multiplying 2 or 3. We can add 1 with the previous number.

For example, 10 can be 5x2 or 9+1. So effectively you should consider 2 cases.

dp[i] = min(dp[i // 2], dp[i // 3]) + 1

So my solution is:

dp = [0 for _ in range(10**6 + 1)]  # Using 10**6 for clarity
n = int(input())
dp[1] = 0

for i in range(2, n + 1):
    if i % 2 == 0 and i % 3 == 0:
        dp[i] = min(dp[i // 2], dp[i // 3]) + 1
    elif i % 2 == 0:
        dp[i] = min(dp[i // 2],dp[i - 1]) + 1
    elif i % 3 == 0:
        dp[i] = min(dp[i // 3],dp[i - 1]) + 1
    else:
        dp[i] = dp[i - 1] + 1

print(dp[n])

Model solution

This solution below is more efficient in calculating. It is exactly same as my logic but it sequentially checks the conditions. It first initialises the dp values as dp[-1]+1. Then, through the 2 if statements, it checks for the divisibility condition. If it is divisible by BOTH 2 and 3, these 2 if statements check for this too.

x=int(input()) # 수 입력받기
d=[0]*(x+1) # 1-based
for i in range(2,x+1): # 2부터 x까지 반복
    d[i]=d[i-1]+1 # 1을 빼는 연산 -> 1회 진행
    if i%2==0: # 2로 나누어 떨어질 때, 2로 나누는 연산
        d[i]=min(d[i],d[i//2]+1)
    if i%3==0: # 3으로 나누어 떨어질 때, 3으로 나누는 연산
        d[i]=min(d[i],d[i//3]+1)
print(d[x])

you can do top-down too like

x=int(input())
dp={1:0}
def rec(n):
    if n in dp.keys():
        return dp[n]
    if (n%3==0) and (n%2==0):
        dp[n]=min(rec(n//3)+1, rec(n//2)+1)
    elif n%3==0:
        dp[n]=min(rec(n//3)+1, rec(n-1)+1)
    elif n%2==0:
        dp[n]=min(rec(n//2)+1, rec(n-1)+1)
    else:
        dp[n]=rec(n-1)+1
    return dp[n]
print(rec(x))

Complexity

This bottom-top approach:

• The loop runs from i = 2 to i = x, which is a total of x - 1 iterations.
• Inside the loop, there are constant-time operations (addition, modulo operations, and comparisons).

Therefore, the overall time complexity of this code is O(x).

The space complexity is O(x) as well because the d list stores values for each number from 1 to x.

So, both the time and space complexity are linear in terms of the input value x.