BOJ ATM, 2xn타일링(1,2), FourSquares

1. BOJ 11399 ATM

실버 3  https://www.acmicpc.net/problem/11399

코드

import sys
input = sys.stdin.readline
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
for i in range(1, N):
    arr[i] += arr[i-1]
print(sum(arr))

설명

오름차순으로 정렬 후 누적합의 합을 구해서 풀 수 있었다. 

2. BOJ 11726 2xn타일링

실버 3, DP  https://www.acmicpc.net/problem/11726

코드

N = int(input())
dp = [0 for _ in range(1001)]
dp[1] = 1
dp[2] = 2
for i in range(3, len(dp)):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[N]%10007)

설명

dp[i] = dp[i-1] + dp[i-2] 
i번째 타일의 경우의 수는 dp[i-1]에서 1x2 하나 추가하는 것과 dp[i-2]에서 (2x1)2세트 하나를 추가하는 것과 같다. 

3. BOJ 11727 2xn타일링2

실버 3, DP  https://www.acmicpc.net/problem/11727

코드

N = int(input())
dp = [0 for _ in range(1001)]
dp[1]=1
dp[2]=3
for i in range(3, 1001):
    dp[i] = dp[i-1]+2*dp[i-2]
print(dp[N]%10007)

설명

dp[i] = dp[i-1] + 2*dp[i-2] 
i번째 타일의 경우의 수는 dp[i-1]에서 1x2 하나 추가하는 것과 dp[i-2]에서 2x2 또는 (2x1)2개를 추가하는 것의 합이다. 
따라서 dp[i-2]는 2배가 된다. 

4. BOJ 

실버 4, DP  https://www.acmicpc.net/problem/17626

코드

N = int(input())
dp = [0, 1]
for i in range(2, N+1):
    ans = 5e5
    for j in range(1, i+1):
        if (j**2)>i:
            break
        else:
            ans = min(ans, dp[i-(j**2)])
    dp.append(ans+1)
print(dp[N])