[백준 알고리즘/Python] 1912 연속합

문제

 

 

문제이해

만약 11이라면 3^2, 2^2, 1^1이 몇개있는지 확인해서 가장 적은 수를 찾으면 됩니다.

예를 들면 11에서 3^2가 몇개있는지 확인하려면 10자리에 +1을 하면 됩니다. 

2^2가 몇개 있는지 확인하려면 7자리에 +1을 하면 됩니다. 

1^1가 몇개 있는지 확인하려면 2자리에 +1을 하면 됩니다.

 

1을 더하는 이유는 나머지 dp[x] +  x*2 로 더하는 경우 (1가지) 의 경우를 더한다고 볼 수 있습니다.

 

예를 들면 

11을 구할 때

• 10 + 1하면 됩니다.
• 7 + 2^2 하면 됩니다.
• 2 + 3^3하면 됩니다.

위 3개중에 가장 작은 경우의 수를 가진것을 뽑으면 됩니다.

 

코드

n = int(input())
dp = [i for i in range(n+1)]


for i in range(1, n+1):
    for j in range(1,i):
        if(j*j)>i:
            break
        if( dp[i] > dp[i-j*j] + 1):
            dp[i] = dp[i-j*j] + 1

print(dp[n])

11을 측정하는데 4^2인 16을 볼필요는 없습니다. 그래서 

if(j*j)>i:
            break

가 들어갔습니다.

 

더 작은 값을 원하니

if( dp[i] > dp[i-j*j] + 1):
            dp[i] = dp[i-j*j] + 1

만약 필요로 하는 자리의 값이 더 작다면 그대로 넣어줍니다.