백준 1463 문제 풀이 python

🐒 1로 만들기

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

✍ 나의 풀이 (최적화 전)

dp = [i for i in range(1000001)]

dp[1] = 0
dp[2] = 1
dp[3] = 1

n = int(input())

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

print(dp[n])

1시간 3분이 걸려서 푼 문제이다.

풀고나서 다른 사람들 풀이들과 비교하니 메모리나 처리시간이 많이 차이난다..

---

🧠 문제 이해

입력된 정수가 1이 되기까지 연산을 하는 횟수의 최솟값을 출력해야한다.

연산의 종류는 다음 세가지이다.

• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• 1을 뺀다.

1부터 n까지의 숫자들의 최소연산 횟수들을 저장해서 다음 계산에 이용한다.

DP 테이블

dp = [i for i in range(1000001)]
	# n까지의 각 숫자마다 연산을 최대로 사용하는 경우(-1-1-1..)를 저장
    
dp[1] = 0 		  # 1은 이미 1이므로 연산이 일어나지 않음
dp[2] = 1		 # 2는 2로 나누거나 1을 뺴서 한번만에 1이 될 수 있음 
dp[3] = 1		# 3은 3으로 나누면 1이 되서 한번만에 1이 될 수 있음 

min함수를 통해서 세가지 연산들 중에 최소횟수가 dp[i]에 저장될 수 있게한다.

n = int(input())

for i in range(4,n+1):
    if i % 3 == 0:
        dp[i] = min(dp[i],dp[i//3]+1)
    if i % 2 == 0:
        dp[i] = min(dp[i],dp[i//2]+1)
    if i % 3 or i % 2:  # 3 또는 2로 나눴을때의 나머지가 존재하면
        dp[i] = min(dp[i],dp[i-1]+1)

print(dp[n])

이렇게 정답은 맞았는데.. 다른 사람들 코드보다 시간,공간복잡도가 크다..

찝찝하다..

---

🛠 리팩토링

정답은 맞췄지만 더 나아가 메모리 사용과 처리시간을 줄이고 싶었다.

나의 코드를 들여다보다 아이디어가 떠올랐다.

1을 빠지는 연산을 기본값으로 두고, 2 또는 3으로 나누는 연산과 최소횟수 비교를 하면 깔끔해질것 같아서 코드를 고쳐보았다.

dp = [0] * 1000001 
  # dp = [0] * (n+1) 로 바꾸고싶은데 인덱스에러가 발생한다..

dp[1] = 0
dp[2] = 1
dp[3] = 1

n = int(input())

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

print(dp[n])

메모리 사용과 처리시간을 대폭 감소시킬 수 있었다! 😊

---

후기

DP는 어렵워