acmicpc.net 2302(DP), 2550(DP, LIS), 2643(DP, LIS), 2225(DP)

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

일단 문제를 어떻게 풀까 생각해보면 예시대로 4,7번이 고정좌석이라면 

1~3번의 경우의수 * 5,6의 경우의수 * 8,9의 경우의수 가 답인걸 알수있다. 그럼 여기서 더 들어가서

1~3번의 경우의 수는 어떻게 구할수 있을까? 노가다 결과 피보나치수임을 깨달았다.

좌석이 1개일경우 경우의수는 1개, 2개는 2개, 3개는 3개, 4개는 5개, .....

여기까지 생각하면 다 푼거다.

# -*- encoding: cp949 -*-
dp = [0 for i in xrange(41)]
n=input()
m=input()
m_list=[input() for i in xrange(m)]
dp[1] = 1
dp[2] = 2
for i in xrange(3,n+1):
    dp[i] = dp[i-1] + dp[i-2]
answer = 1
before = 0
for i in xrange(m):
    if m_list[i]-before-1!=0:
        answer *= dp[m_list[i] - before - 1]
    before = m_list[i]
if n-before!=0:
    answer *= dp[n - before]
print answer

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

lis문제는 앞에 지겹도록 다뤄봤으니 설명은 따로 안적음.

# -*- encoding: cp949 -*-
from bisect import bisect_left
def lis(line):
    dp = [0 for i in xrange(10002)]
    fr = [0 for i in xrange(10003)]
    size = 0
    for i in xrange(len(line)):
        h = bisect_left(dp[:size],line[i])
        if h==size: size += 1
        dp[h] = line[i]
        fr[dp[h]] = dp[h-1] if h else 0
     
    i=dp[size-1]
    lis_list = []
    while i:
        lis_list.insert(0,i)
        i = fr[i]
    return lis_list

n=input()
a=map(int,raw_input().split())
b=map(int,raw_input().split())
c = [[a.index(i)+1,b.index(i)+1] for i in xrange(1,n+1)]
line = map(lambda x:x[1],sorted(c,key=lambda x:x[0]))
l = lis(line)
print len(l)
z = sorted([b[i-1] for i in l])
for i in z:
    print i,

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

lis문제라고 감을 잡을 수 있다. 

1. 색종이를 90도 돌리는것이 가능하므로 색종이들을 [짧은변,긴변] 형태로 놓은 후 긴변을 기준으로 첫번째 정렬, 짧은변 기준으로 두번째 정렬을 해준다.

2. O(N^2) LIS소스로 LIS를 구한다. 색종이가 최대 100개이기때문에 N^2의 시간복잡도로도 충분하다. 색종이가 1,3 1,3일경우 2개로 세줘야한다. LIS는 항상 1이라도 증가하는 형태인데 이건 <=로 해줘야 한다. 아래 소스보면 이해할듯.

# -*- encoding: cp949 -*-
from bisect import bisect_left
dp = [-1 for i in xrange(102)]
def lis(s):
    if dp[s+1]!=-1:
        return dp[s+1]

    dp[s+1] = 0
    for i in range(s+1,n):
        if s==-1 or a[s][0] <= a[i][0]:
            dp[s+1] = max(dp[s+1], lis(i)+1)
    return dp[s+1]

n=input()
a=[map(int,raw_input().split()) for i in xrange(n)]
a = sorted([[min(i),max(i)] for i in a],key=lambda x:(x[1],x[0]))
#print 'a =',a
print lis(-1)

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

잘 생각해보자. 5를 숫자 4개로 만드는 방법을 구한다고 하자.

5를 만들려면 (0,5), (1,4), (2,3), (3,2), (4,1), (5,0)의 6가지가 있다. 이걸 구하려면 

(0을 숫자 2개로 만드는방법+5를 숫자 2개로만드는방법) + (1을 2개로+4를 2개로) + (2를 2개로+3을 2개로) + ..... (5를 숫자 2개로 만드는방법 + 0을 숫자 2개로 만드는 방법) 의 총합이 5를 숫자 4개로 만드는 방법이다. 

# -*- encoding: cp949 -*-
dp = [[0 for i in xrange(202)] for j in xrange(202)]
n,k=map(int,raw_input().split())
mod = 1000000000

for i in xrange(n+1):
    dp[1][i] = 1

for i in xrange(2,k+1):
    for j in xrange(n+1):
        dp[i][j] = (dp[i][j] + sum(dp[i-1][:j+1]))%mod

print dp[k][n]%mod