행복한 개구리

n = int(input()) dp = [[0 for i in range(10)] for i in range(101)] for i in range(1, 10): dp[1][i] = 1 for i in range(2, n+1): for j in range(10): if j == 0: dp[i][j] = dp[i-1][1] elif j == 9: dp[i][j] = dp[i-1][8] else: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[n]) % 1000000000) n자릿수의 경우의 수를 각 수(0~9)마다 저장하기위해 dp리스트를 만들었습니다. 규칙을 이끌어내기 위해 1자릿수의 정답들은 리스트에 지정해줍니다. 반복을 통해서 초깃값을 지정했습니다. 표를 ..

N = int(input()) # dp의 범위가 0 ~ n까지 저장할 수 있도록 범위를 N+1까지 지정합니다. dp = [0 for i in range(N+1)] for n in range(2, N+1): # n에서 1을 뺀 후 dp[n-1]의 과정을 실행할 때의 값(해당 수의 연산 최댓값) dp[n] = dp[n-1] + 1 # n을 3으로 나눌 수 있을 때 if n % 3 == 0: dp[n] = min(dp[n], dp[n//3] + 1) # n을 2로 나눌 수 있을 때 if n % 2 == 0: dp[n] = min(dp[n], dp[n//2] + 1) # n의 연산 최솟값 출력 print(dp[N]) 우선 입력받은 수까지 연산 최솟값을 저장할 dp리스트를 만듭니다 dp리스트의 인덱스는 주어진 정..

n = int(input()) step = [0 for i in range(300)] dp = [0 for i in range(300)] for i in range(n): step[i] = int(input()) dp[0], dp[1], dp[2] = step[0], step[0] + step[1], max(step[1] + step[2], step[0] + step[2]) for i in range(3, n): dp[i] = max(dp[i-3] + step[i-1] + step[i], dp[i-2] + step[i]) print(dp[n-1]) 규칙을 찾는 것이 우선입니다. step에는 각 계단의 비용을, dp에는 각 계단까지의 최댓값을 저장합니다. 1번째, 2번째 계단의 최댓값은 step[0], s..

더보기 더보기 n = int(input()) tri = [list(map(int, input().split())) for i in range(n)] idx = tri[1].index(max(tri[1])) for i in range(1, n): tri[i][idx] += max(tri[i-1][idx-1:idx+1]) idx = tri[i].index(max(tri[i])) print(max(tri[-1])) 경로에 있는 최댓값만 골라서 더하는 방식으로 작성했습니다. 하지만 지나치는 경로의 합이 최대인 것을 구하는 것이 문제이므로 각 줄마다의 경로에서 최댓값을 고르는 것이 정답은 아닙니다. n = int(input()) tri = [list(map(int, input().split())) for i in..

N = int(input()) rgb = [list(map(int, input().split())) for i in range(N)] for i in range(1, N): rgb[i][0] += min(rgb[i-1][1], rgb[i-1][2]) rgb[i][1] += min(rgb[i-1][0], rgb[i-1][2]) rgb[i][2] += min(rgb[i-1][0], rgb[i-1][1]) print(min(rgb[-1])) rgb 리스트에 주어진 rgb의 비용을 리스트로 저장해줍니다. 그리고 for문에 세가지 분기를 정하여 만약 i번째 집이 r,g,b 일경우에 색이 겹치지 않는 i-1번째 집의 최소비용은 얼마인지 rgb[i]에 계속하여 저장하며 활용합니다. rgb리스트에서 가장 마지막요소인 ..

T = int(input()) dp = [0 for i in range(100)] for i in range(5): if i < 3: dp[i] = 1 else: dp[i] = 2 for i in range(T): N = int(input()) for i in range(5, N): dp[i] = dp[i-5] + dp[i-1] print(dp[N-1]) 수열의 규칙을 찾아봅시다. P(N)에서 N이 5일때까지는 별 규칙이 없지만 N이 5이상이라면 P(N) = P(N-1) + P(N-5)의 규칙을 가집니다. dp리스트를 입력받을 수 있는 범위에 맞게 생성해줍니다. 값은 0으로 설정합니다. 지정한 인덱스의 값이 0이라면 아직 P(N)이 구해지지 않은 상태인 것입니다. P(N)에서 N이 1~5일 때는 규칙없이..