[python] 백준 11055 가장 큰 증가 부분 수열
https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 해결 전통적인 dp문제 dp[n]을 n을 마지막으로 포함하는 부분 증가 수열중 합이 가장 큰 수를 나타낸다고 하자. 이 때 들어가는 수열중 n 이전 마지막 수를 i라 할 때 dp[n] = max(dp[i]+A[n], dp[n])이 될 것이다. 따라서 이 것을 생각하고 풀면 끝 CODE import sys input = sys.stdi..
2022. 12. 29.
[python] 백준 11722 가장 긴 감소하는 부분 수열
https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 문제 해결 수열에서 부분 수열 중 감소 수열이 되도록 뽑았을 때 가장 긴 수열을 찾는 문제 n번째 수는 뽑힐 수도 있고 안 뽑힐 수도 있음 n번째 수가 뽑힌다고 가정할 때 n-1번까지 수열중 가장 긴 수열에 +1이 되는 것이며 마지막 수보다 n번째 수가 작아야한다. n번째 수를 넣었을 때 가장 긴 수열을 dp[n]이라고 하..
2022. 12. 29.
