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

문제

실버 3 - https://www.acmicpc.net/problem/1463

코드 구현

N = int(input())
dp = [0] * (N + 1)

for i in range(2, N + 1):   # 2부터 N까지 dp[i]에는 i가 1이 되기 위한 최소연산횟수를 담게된다.
    dp[i] = dp[i - 1] + 1   # 1을 빼는 연산 (1회 진행)
    
		if(i % 2 == 0):         # 근데 i가 만약 2로 나누어떨어지는 수라면
        dp[i] = min(dp[i], dp[i//2] + 1)    # 2로 나누는 경우의수에 대한 최소연산횟수가 어떤건지 비교하기
        # (여기서 dp[i//2] + 1 == i를 2로 나눈 값이 1이 되는데 걸리는 최소연산횟수 + i를 2로 나누는 연산횟수 1회)
    
		if(i % 3 == 0):         # i가 만약 3으로 나누어떨어지는 수라면
        dp[i] = min(dp[i], dp[i // 3] + 1)
        # (여기서 dp[i//3] + 1 == i를 3으로 나눈 값이 1이 되는데 걸리는 최소연산횟수 + i를 3으로 나누는 연산횟수 1회)

print(dp[N])

풀이

• 참고 : https://bio-info.tistory.com/159
• 2부터 N까지 dp[i]에는 i가 1이 되기 위한 최소연산횟수를 담게된다.
• 우선 dp[i]를 d[i-1] (i-1이 1이 되는데 필요한 최소한의 연산) + 1 (i에서 1을 빼서 i-1이 되는데 필요한 연산 횟수 1회)로 초기화 해준다.
• 만약 2로 나누어떨어지는 수라면 → 2로 나누는 경우의 수에 대한 최소연산횟수가 어떤건지 비교하기
  • dp[i//2] + 1 == i를 2로 나눈 값이 1이 되는데 걸리는 최소연산횟수 + i를 2로 나누는 연산횟수 1회
• 3으로 나누어떨어지는 수여도 똑같이 비교하여 업데이트 해준다.