문제요약 나의 코드 및 설명 n = int(input()) num_list = [0] + list(map(int, input().split())) dp = [0] * (n+1) #dp테이블에 연속된 수들의 합 저장(만약 연속된 수들의 합이 음수라면 0 저장) ans = 0 for i in range(1, n+1): #dp테이블 채우기 dp[i] = dp[i-1] + num_list[i] #dp[i](현재 인덱스)는 이전까지 저장된 합(dp[i-1] + 현재숫자(num_list[i]) if dp[i] < 0: #만약 연속된 수들의 합이 음수가 된다면 dp[i] = 0 #음수말고 그냥 안더하는 걸 선택. 0으로 갱신 if max(num_list[1:]) < 0: #수열들이 음수로만 구성되어 있다면, ans ..
문제요약 나의 코드 및 설명 n = int(input()) num_list = [0] + list(map(int, input().split())) dp = [0] * (n+1) for i in range(n+1): #dp 테이블 채우기 mx = 0 for j in range(i): #dp 처음 인덱스부터 현재 인덱스-1 까지 값 비교 if num_list[i] > num_list[j]: #만약 작은 숫자라면, mx = max(mx, dp[j]) #최대값을 찾는다 dp[i] = mx + 1 #찾은 최대값에서 +1 해준 것이 dp[i] 값 print(max(dp)) 피드백 DP 알고리즘 연습을 위해 풀어본 문제. LIS는 꽤 유명한 문제라고 한다. 누적된 최대 길이를 저장하는 dp 테이블을 만들고, for문..
문제요약 나의 코드 및 설명 n = int(input()) dp = [0] * (n+1) for i in range(2, n+1): dp[i] = dp[i-1] + 1 # 1로 더하는 경우 (dp[i-1] + 1) -> dp의 값에는 최소값이 저장되기 때문에 가 if i % 2 == 0: #2로 나누어 떨어지는 경우 dp[i] = min(dp[i], dp[i//2] + 1) #dp[i//2]에 저장된 값+1 과 dp[i](1로 더하는 경우) 비교 if i % 3 == 0: #3으로 나누어 떨어지는 경우 dp[i] = min(dp[i], dp[i//3] + 1) #dp[i//3]에 저장된 값+1 과 dp[i](1로 더하는 경우) 비교 print(dp[n]) 피드백 DFS, BFS, 백트래킹에 이어 DP 연..
