본문 바로가기
반응형

알고리즘/dynamic programming27

[백준][Python] 1965번 상자넣기 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 코드 n = int(input()) n_list = list(map(int,input().split())) dp = [1 for _ in range(n)] for i in range(1,n): for j in range(i): if n_list[i] > n_list[j]: dp[i] = max(dp[i],dp[j] + 1) print(max(dp)) 2022. 12. 9.
[백준][Python] 11048번 이동하기 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 코드 n,m = map(int,input().split()) l = [list(map(int,input().split())) for _ in range(n)] dp = [[0]*(m+1) for _ in range(n+1)] for i in range(1,n+1): for j in range(1,m+1): dp[i][j] = l[i-1][j-1] + max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]) print(dp[n][m]) 2022. 12. 6.
[백준][Python] 11057번 오르막 수 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 코드 n = int(input()) dp = [1]*10 for i in range(n-1): for j in range(1,10): dp[j] += dp[j-1] print(sum(dp)%10007) 2022. 12. 5.
[백준][Python] 19947번 투자의 귀재 배주형 19947번: 투자의 귀재 배주형 2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다. 주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 1년마다 5%의 이율을 얻는 투자 ( www.acmicpc.net 코드 h,y = map(int,input().split()) dp = [0 for _ in range(y+1)] dp[0] = h for i in range(1,y+1): if i >= 5: dp[i] = int(max(dp[i-1]*1.05, dp[i-3]*1.2, dp[i-5]*1.35)) elif i >= 3: dp[i] = int(max(dp[i-1]*1.05, dp[i-3]*1.2)) else: dp[i] = int(dp[i-1]*1.05.. 2022. 7. 25.
반응형

티스토리툴바