시작이 반

현재 값(A[i]에서 이전 값들(A[0] ~ A[i-1])을 보면서 현재값보다 작으면서 dp(이전에 구한값)값이 가장 큰 값을 찾는다. n = int(input()) a = list(map(int, input().split())) dp = [0] * n def sequence(): dp[0] = a[0] for i in range(1, n): max_value = 0 for j in range(i): if a[i] > a[j]: if abs(a[i] - a[j]) != 0: max_value = max(max_value, dp[j]) max_index = dp.index(max_value) dp[i] = dp[max_index] + a[i] sequence() print(max(dp))

*연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 처음에는 계단오르기와 같은 방식으로 풀었지만 계단오르기는 1칸 뛰어서 올라갈수 있는데 이문제는 몇칸이든 뛰어서 시음을 할 수있다. 이는 n잔 주워졌을떄 n-1잔 뛰어서 시음을 할 수 있다. 때문에 배열을 n+1 x n 개 만들어서 풀었지만 메모리 초과가 나왔다. 메모리 제한이 128MB이다 입력 제한이 10000인데 10001 x 10000 개 만들어버리면 당연히 메모리 초과가 나온다. 다시 생각했을때 최대 2잔까지 건너뛰어서 마셔도 최대값을 구할수 있다고 생각했다. 6 1000 1000 1 1 1000 1000 이렇게 있을때 1, 2, 5, 6을 마시는게 최대값이다. 7 1000 1000 1 1 1 1000 1000 이렇게 있다면 1, 2, 4, 6,..

dp[] 리스트의 크기를 n+1개 만들고 10^6으로 초기화 한다. dp[n] 부터 시작한다. dp[10] : 시작 연산 횟수는 0으로 초기화 이제 갈수 있는 정수가 3가지 있다. 1. 3으로 나누어 떨어지면, 3으로 나눈값 2. 2로 나누어 떨어지면, 2로 나눈값 3. 1을 뺀값 10에서는 9, 5 로 갈 수 있다. 연산된 값에 있는 숫자와 (처음 나온 숫자면 10^6이 있을 것이고, 이전에 연산된 숫자면 연산 횟수가 있을 것이다) 이전 연산횟수 +1 중 작은 값을 저장한다. x = int(input()) dp = [1e6] * (x + 1) dp[x] = 0 def make_one(): for i in range(x, 0, -1): if i % 2 == 0: dp[i // 2] = min(dp[i] ..

현재 계단으로 온 경우는 2가지이다. 1. 1단계전 계단에서 온경우 2. 2단계전 계단에서 온경우 1번일 경우 연속으로 계단을 올라갈 수 없으므로 이전에 2단계전 계단에서 올라온 경우에 현재 계단의 비용을 더한다. 2번일 경우 2단계전 계단에서 온경우의 최대값과 현재 계단의 비용을 더한다. cost[0][0]. cost[0][1] 은 0단계 임으로 0이다 i, j 0 : 연속으로 계단을 1칸씩 올라온경우 ex) 1->2 1 : 2단계씩 계단을 오른 경우 1 cost[1] cost[1] 2 dp[1][1] + cost[2] max(dp[0][0], dp[0][1]) + cost[2] 3 dp[2][1] + cost[3] max(dp[1][0], dp[1][1]) + cost[3] 4 dp[3][1] + c..

트리형태.. 이런형태의 리스트로 만들 수 있다. triangle[i][j] j i 0 1 2 3 4 0 7 1 3 8 2 8 1 0 3 2 7 4 4 4 4 5 2 6 5 dp[i][j] j i 0 1 2 3 4 0 triangle[i][j] 1 dp[i-1][ j ] + triangle[ i ][ j ] dp[i-1][ j ] + triangle[ i ][ j ] 2 dp[i-1][ j ] + triangle[ i ][ j ] MAX(dp[i-1][j-1], dp[i-1][ j ]) + triangle[ i ][ j ] dp[i-1][ j ] + triangle[ i ][ j ] 3 dp[i-1][ j ] + triangle[ i ][ j ] MAX(dp[i-1][j-1], dp[i-1][ j ]) +..

현재 선택한 색에 따라 나뉘어 지는 경우의 수가 2가지씩 존재한다. 마찬가지로 다음 상태는 이전상태에서 올 수 있는 경우의 수가 2가지 존재한다. 때문에 다음 상태는 이전 상태(2가지)중 작은 값을 찾아서 더해주면 된다. -> 2차원 배열로 dp를 만들어준다. 첫번째 행은 첫번째 집들의 비용을 넣으면 된다. import copy n = int(input()) cost = [list(map(int, input().split())) for _ in range(n)] dp = [[10001] * 3 for _ in range(n)] def RGB(): for i in range(n): for j in range(3): if i == 0: dp[i][j] = cost[i][j] else: if j == 0: d..

삼각형을 계속 이어나가면서 규칙을 찾는 문제이다. 내가 구한 점화식은 f(1) = 1 f(2) = 1 f(3) = 1 f(4) = f(3) + f(1) f(5) = f(4) f(6) = f(5) + f(1) f(7) = f(6) + f(2) f(8) = f(7) + f(3) f(5)부터 규칙을 찾을 수 있었다.. t = int(input()) def padovan(n): dp = [-1] * n for i in range(n): if i < 3: dp[i] = 1 elif i == 3: dp[i] = dp[i-1] + dp[i-2] else: if i-5 < 0: dp[i] = dp[i-1] else: dp[i] = dp[i-1] + dp[i-5] return dp[n-1] for _ in range(t..

금방 풀릴줄 알았지만 엄청 오래 걸렸다...(항상 이런듯) 처음에 집위치에서 상하좌우 모든 곳을 재귀를 돌려서 체력을 계산하면서 민트 초코가 있는곳 까지 가고 집에 도달하면 return 을 하는 식으로 하였지만 시간 초과가 떴다... 생각해보니 모든 경로를 탐색하기 때문에 갔던곳을 또간다. 이 사실을 알지만 처음 푼 방법에서 어떻게 고쳐야 할지 모르겠어서 다 지우고 처음부터 다시 풀기로 하였다. 첫풀이 n, hp, hp_puls = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(n)] vistied = [[False] * n for _ in range(n)] dx = [-1, 1, 0, 0] dy = [0..