💡문제
수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.
예제입력
10
1 100 2 50 60 3 5 6 7 8예제출력
113📖내가 작성한 Code
import sys
"""
1. 가장 긴거 아님 가장 큰거임
"""
def largest_increasing_sub(n, array):
dp = array.copy()
for i in range(n):
for j in range(i):
if array[i] > array[j]:
dp[i] = max(dp[i], dp[j] + array[i])
return max(dp)
def main():
inputs = list(map(int, sys.stdin.read().split()))
print(largest_increasing_sub(inputs[0], inputs[1:]))
if __name__ == "__main__":
main()
✍️풀이과정
간단한 DP문제. 그런데 놀랍게도 처음에는 시간 초과가 났다.
입력 수가 많아지면 모든 합에 대하여 지수적으로 증가하는 걸 생각하지 못했다. 가능한 모든 부분 수열의 합을 구하려는 아이디어에 빠져 이런 이상한 코드를 만든 것.
시간 1초. N의 최대 길이는 1000. 따라서 그냥 이중 반복문을 돌려도 괜찮은 문제를 틀려버린 것이다. 설계를 좀 더 잘 할 필요가 있다. 최근에 너무 자만 한 듯하다.
아래에는 다른 사람의 코드가 있다.
N = int(input())
A = list(map(int, input().split()))
dp = [0] * 1001 # 0 <= i <= 999
for a in A:
dp[a] = max(dp[:a]) + a
print(max(dp))매우 아름답다. 마지막 원소가 a인 수열로 저장하여 깔끔하게 접근하였다. 좀 더 공부하고 자만하지 않는 시간이 되었다.
🧠 코드 리뷰
-
함수명 및 변수명: 함수 이름 largest_increasing_sub는 문제의 성격(증가하는 부분 수열의 합)과 더 명확하게 연결되도록
예를 들어, largest_increasing_subsequence_sum 또는 max_increasing_subsequence_sum과 같이 명명하면 이해하기 더 쉽습니다. -
주석 추가: 코드에 이미 간단한 주석이 포함되어 있지만, 함수에 간단한 docstring(설명, 파라미터 및 반환 값 설명)을 추가하면 향후 유지보수 시 더욱 도움이 됩니다.
🛠️AI 개선 코드
import sys
def largest_increasing_subsequence_sum(n, sequence):
"""
주어진 수열에서 증가하는 부분 수열 중 합이 가장 큰 값을 구한다.
Parameters:
n (int): 수열의 길이
sequence (List[int]): 정수로 이루어진 수열
Returns:
int: 증가하는 부분 수열 중 최대 합
"""
dp = sequence.copy()
for i in range(n):
for j in range(i):
if sequence[i] > sequence[j]:
dp[i] = max(dp[i], dp[j] + sequence[i])
return max(dp)
def main():
inputs = list(map(int, sys.stdin.read().split()))
n = inputs[0]
sequence = inputs[1:]
print(largest_increasing_subsequence_sum(n, sequence))
if __name__ == "__main__":
main()
💻결과
🖱️참고 링크
