흙금이네 블로그

아이디어 동적 계획법으로 고객 수에 따른 최소 비용을 계산한다. 풀이 #1 (Python) 0으로 채운 (N+1)×100 크기의 2차원 리스트 dp를 생성한다. dp[i][j]에는 i번 사람 차례에서 체력이 j일 때 얻을 수 있는 최대 기쁨을 저장한다. 이중 for문에서 체력이 0(인사를 한번도 하지 않은 경우)이거나 dp[i][j]에 저장된 값이 있을 때 현재 사람에게 인사한 후의 체력이 100 미만이면 인사한 후의 상태인 dp[i+1][j+L[i]]에 인사한 후의 기쁨을 저장하고, 인사하기 전과 비교해 인사하기 전의 기쁨이 더 크다면 dp[i+1][j]에 인사하기 전의 기쁨 dp[i][j]를 저장한다. import sys input = sys.stdin.readline N = int(input()) ..