[COS Pro 1급, Python] 5차 9번 : 몇번 연산을 해야 하나요

문제 유형

 코딩

난이도

 hard

Note 

 1. DP 문제. 2*N 타일링 문제. <- 사실 이 문제라는 것을 파악하는게 핵심. DP문제 많이 푸는 연습만이 살길... 

 2. dp 배열. 인덱스는 target 수를 의미.

 3. 1을 더하는 연산, 1을 빼는 연산, 2를 곱하는 연산을 수행하면서 dp 배열의 target 값에 최솟값을 저장. 

 

Code

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
#DP 2*n+1 타일링

def solution(number, target):
	
    dp = [-1]*(2*target+1)
	
    for i in range(1, number+1):
        dp[i] = number - i
        dp[i*2] = dp[i] + 1
		
    dp[number+1] = 1

    for i in range(number+2, target+1):
        min_num = min(dp[i-1]+1, dp[i//2]+1) if (i % 2 == 0) and (i//2 >= number) else dp[i-1]+1
			
        if dp[i+1] != -1:
            min_num = min(min_num, dp[i+1]+1)

        if dp[i] != -1:
            min_num = min(min_num, dp[i])
			
        dp[i] = min_num
        dp[i*2] = min_num+1

    print(dp)

    return dp[target]

number1 = 5
target1 = 9
ret1 = solution(number1, target1)

print("solution 함수의 반환 값은", ret1, "입니다.")

number2 = 3
target2 = 11
ret2 = solution(number2, target2)

print("solution 함수의 반환 값은", ret2, "입니다.")

 

※ 가끔 코드 중 print(~)가 있습니다. 정리 못한 점 죄송합니다.