acmicpc.net 1535(배낭 문제, DP), 1915(DP), 1562(비트마스크, DP)

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

배낭 문제. 체력이 0이되면 죽은것이므로 초기 체력을 100이아닌 99로 설정해준다.

# -*- encoding: cp949 -*-
import sys
sys.setrecursionlimit(1000000)
def getmax(capacity, index):
    ret = 0
    if index == n:
        return 0
    unselected = getmax(capacity, index+1)
    selected = 0
    if capacity >= weight[index]:
        selected = getmax(capacity-weight[index], index+1) + value[index]
    return max(unselected, selected)
 
n=input()
weight = map(int,raw_input().split())
value = map(int,raw_input().split())
capacity = 99
index = 0
print getmax(capacity, index)

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

기초 dp문제.

# -*- encoding: cp949 -*-
dp = [[0 for j in xrange(1002)] for i in xrange(1002)]
n,m=map(int,raw_input().split())
arr = [map(int,raw_input()) for i in xrange(n)]

for i in xrange(1,n+1):
    for j in xrange(1,m+1):
        if arr[i-1][j-1]==1:
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

print max(map(max, dp))**2

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

어렵다. 진짜 한참걸렸다.. 방법론을 몰랐으면 못풀었을듯.

# -*- encoding: cp949 -*-
import sys
sys.setrecursionlimit(100000000)
def sol(index, now, visited):
    if now < 0 or now > 9: #범위 넘어가면 0
        return 0
    elif index==n: #끝까지 갔는데
        if(((1<<10)-1)==visited): #전체 다 방문했으면 1리턴
            return 1
        return 0
    ret = dp[index][now][visited] #현재.
    if ret!=-1: return ret 
    if now==0: dp[index][now][visited] = sol(index+1, now+1, visited | (1 << (now + 1))) + sol(index+1, now-1, visited) %1000000000 #0일경우 음수 쉬프트에 대해서 예외처리해줘야된다.
    else: dp[index][now][visited] = sol(index+1, now+1, visited | (1 << (now + 1))) + sol(index+1, now-1, visited | (1 << (now - 1))) %1000000000
    
    return dp[index][now][visited]%1000000000

n=input()
ans = 0
dp = [[[-1 for i in xrange(2**11)] for j in xrange(10)] for k in xrange(102)] #100번까지 n입력가능, 1~9까지, 1111111111 방문을 위한 마지막 리스트
for i in xrange(1,10): #1~9까지 다 방문해봄.
    ans += sol(1,i,1<<i) #n=1,1~9,1~9를 방문함을 표시.
    ans %= 1000000000
print ans