acmicpc.net 2805(이분 탐색), 9184(DP 메모이제이션 기초), 2688(DP)

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

이분 탐색으로 찾는다.

n,m=map(int,raw_input().split())
tree = map(int,raw_input().split())
l,h = 0,1000000000

while l < h:
    mid = (l+h)/2
    s = 0
    bl,bh = l,h
    for i in xrange(n):
        if tree[i] > mid:
            s += tree[i]-mid
    if s >= m: l = mid
    else: h = mid
    if bl==l and bh==h:
        break

print l

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

괜찮은 문제 중 하나라고 생각한다. 재귀함수가 있을때 이것을 메모이제이션 하는 방법을 묻는 문제이다.

기초적이지만 유용하다고 생각한다.

# -*- encoding: cp949 -*-
def w(a,b,c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1

    if a > 20 or b > 20 or c > 20:
        dp[20][20][20] = w(20, 20, 20)
        return dp[20][20][20]

    ret = dp[a][b][c]
    if ret!=0: return ret

    if a < b and b < c:
        dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return dp[a][b][c]

    dp[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
    return dp[a][b][c]

while True:
    dp = [[[0 for k in xrange(40)] for j in xrange(40)] for i in xrange(40)]
    a,b,c = map(int,raw_input().split())
    if a==b==c==-1: break
    print 'w({}, {}, {}) = {}'.format(a,b,c,w(a,b,c))

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

쉽다.... 앞의 쉬운 계단수였나 그 문제랑 똑같다.

# -*- encoding: cp949 -*-
dp = [[0 for j in xrange(10)] for i in xrange(65)]
for i in xrange(10):
    dp[1][i] = 1
for i in xrange(2,65):
    for j in xrange(10):
        dp[i][j] += sum(dp[i-1][j:])
for t in xrange(input()):
    n=input()
    print sum(dp[n])