입력 6 6 10 13 9 8 1 연속적으로 3잔을 모두 마실 수 없다는 제한이 걸린 문제이다. n번째에 제한을 두는 문제는 i번째를 기준으로 (i - 1), (i - 2), (i - 3).. 번째를 생각봐야한다. n = int(input()) grape = [0] sum = 0 for _ in range(1, n + 1): grape.append(int(input())) dp = [0, grape[1]] if n > 1: # 포도주가 1잔일 수 있음 dp.append(grape[1] + grape[2]) for i in range(3, n+1): dp.append(max(dp[i-1], dp[i-2] + grape[i], dp[i-3] + grape[i] + grape[i-1])) # 차례로 이번 차례..

10 10 -4 3 1 5 6 -35 12 21 -1 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구해야 한다. 여기서 연속된 몇개의 수는 연속적으로 증가하는 수가 아닌 배열의 인접한 수임에 주의하자 !!!! 만약 연속적인 배열의 값이 모두 양수라면 해당 값들을 모두 더해준다. 이때 현재 인덱스의 배열값이 음수라고 해보자 그 음수 값을 더한 누적 합에 다음 인덱스 배열값을 더하면 다음 인덱스 배열에 있던 기존의 값보다 작아질 수 있다. 입력 예시로 생각해보자 10 6 9 10 15 21 -14 12 33 32 21 + (-35)의 값은 -14이다. 해당 값에 + 12를 하면 -2 값이 나온다. -2 값은 기존의 12 값보다 작으므로 걸러지고 기존 값인 12가 남는다. 만약 여기서 다..

정방향, 역방향 가장 긴 증가하는 수열을 구한뒤 각 dp의 값을 합쳐준다. 이때 -1을 하는 이유는 바이토닉 수열의 변곡점 부분의 dp 값이 2번 카운팅되기 때문이다. N = int(input()) A = list(map(int, input().split())) A.insert(0, 0) dpf = [1] * (N + 1) # 정방향 dpr = [1] * (N + 1) # 역방향 dps = [1] * (N + 1) # 합칠 때 for i in range(1, N + 1): for j in range(1, i): if A[j] < A[i]: dpf[i] = max(dpf[i], dpf[j]+1) for i in range(N, 0, -1): for j in range(N, i, -1): if A[j] < ..

6번 정도 실패하고 반례 테스트케이스 보고 해결한 문제 ㅠ_ㅠ 처음 생각한 코드는 다음과 같다. n = int(input()) a = list(map(int, input().split())) a.insert(0, 0) dp = [0] * (n + 1) dp[1] = a[1] for i in range(1, n + 1): for j in range(1, i): if a[j] < a[i]: dp[i] = max(dp[i], a[i] + dp[j]) # print(dp) print(max(dp)) 해당 코드로 문제에 주어진 입력 예제를 넣었을 때는 정답이 출력되지만 채점시 틀렸다고 떴다. 반례 6 10 20 10 30 20 50 다음과 같이 입력이 주어졌을 때 내가 원했던 dp는 [10, 30, 10, 60,..

풀 때도 이해가 안갔지만 풀이를 보고도 애매한 문제 .. ㅎㅎ 우선 스티커의 위치와 값을 배열로 만들면 다음과 같다. index 0 1 2 3 4 0 50 10 100 20 40 1 30 50 70 10 60 이제 조건을 생각해보자 어떤 자리를 하나 선택하면 그 자리의 상, 하, 좌, 우는 더 이상 쓸 수 없는 스티커가 된다. 예를 들어 50을 선택한다고 하면 양옆의 그 양옆인 10, 30은 더 이상 사용할 수 없게된다. index 0 1 2 3 4 0 50 10 + 30 = 40 max(100, 30) + 100 = 200 max(120, 100) + 20 = 140 max(210, 120) + 40 = 250 1 30 50 + 50 = 100 max(40, 50) + 70 = 120 max(200, ..

상태 트리를 그릴 때 다음을 기준으로 가지를 뻗어나가면 된다. 추가 주어졌을 때 양팔 저울의 좌측에 추를 올림 우측에 추를 올림 해당 추를 사용하지 않고 넘어감 ex) 좌측에 무게 1짜리 추를 올리고 우측에 무게 6짜리 추를 올리면 총 5라는 무게를 측정할 수 있다. def DFS(L, sum): global res if L == n: if 0 < sum