전체 글 (171) 썸네일형 리스트형 [BOJ] [Python] 1932번 : 정수 삼각형 li 리스트와 동일한 위치의 dp 리스트 위치에는, 그 위치까지 계산된 값을 넣었다. num = int(input()) li = [] dp = [] for n in range(num): li.append(list(map(int, input().split()))) if(n != num-1): dp.append([0] * len(li)) dp.append(li[-1]) li.reverse() dp.reverse() for i in range(num): for j in range(len(li[i])-1): dp[i+1][j] = max(dp[i][j], dp[i][j+1]) + li[i+1][j] print(dp[-1][0]) [BOJ] [Python] 2579번 : 계단 오르기 어느 계단이든지, 그 계단을 밟기 위한 방법은 2가지이다. n번째 계단을 예시로 생각해보자. 1. n-2번째와 n번째 밟기 2. n-3번째와 n-1번째, n번째 밟기 첫 번째 방법에서는 n-2번째 계단이, 두 번째 방법에서는 n-3번째 계단이 첫 계단이다. 이 계단들은 그 자리에 오기까지의 값을 dp 리스트에 저장하고 있어야 하고, 계산할 때, 계단의 값이 아닌 dp 값을 더해야 한다. 방법1과 방법2 중 더 큰 값을 골라, n번째 dp에 저장한다. num = int(input()) li = [0] dp = [0] * (num + 1) for n in range(num): li.append(int(input())) for i in range(1, num+1): if(i == 1): dp[1] = li[1.. [BOJ] [Python] 9625번 : BABBA 1) 규칙을 찾아보자 문제에 나온 예시를 그대로 적어보면, F(n) = F(n - 1) + F(n - 2) (n >= 2) 라는 규칙이 보인다. 즉, 피보나치 수열이다. 2) A와 B 관계를 보자 n의 A 개수는 n-1의 B 개수이다. (n >= 1) 피보나치 수열을 재귀함수를 이용했을 때와는 달리, 리스트에 값을 저장하는 식[Memoization]으로 풀었다. num = int(input()) # 피보나치 # [0, 1, ... ] dp = [0] * (num + 1) dp[1] = 1 for i in range(2, num+1): dp[i] = dp[i-1] + dp[i-2] print(dp[num-1], dp[num]) + 추가) 재귀함수를 이용하면 했던 연산을 또 하게 된다. 이전 1 ··· 47 48 49 50 51 52 53 ··· 57 다음
