백준 python 1463번 1로만들기 / 2579번 계단오르기 / 백준 1932번 정수 삼각형

백준 python 1463번 1로만들기

 

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

Python

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] + 1, dp[i // 2])         if i % 3 == 0:             dp[i // 3] = min(dp[i] + 1, dp[i // 3])         dp[i-1] = min(dp[i] + 1, dp[i-1]) make_one() print(dp[1])

 

백준  2579번 계단오르기

 

 

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

반응형

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

 

Python

n = int(input()) cost = [0] dp = [[0] * 2 for _ in range(n + 1)]  # [][0] : 연속, [][1] : 2칸 for _ in range(1, n + 1):     cost.append(int(input())) def stair():     dp[1][0] = cost[1]     dp[1][1] = cost[1]     for i in range(2, n + 1):         for j in range(2):             if j == 0:                 dp[i][j] = dp[i - 1][1] + cost[i]             else:                 dp[i][j] = max(dp[i - 2]) + cost[i] stair() print(max(dp[n]))

 

백준 1932번

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 

 

Python

n = int(input()) triangle = [list(map(int, input().split())) for _ in range(n)] dp = list() for i in range(n):     dp.append([0]*(i+1)) def int_triangle():     global dp     for i in range(n):         for j in range(len(dp[i])):             if i == 0:                 dp[i][j] = triangle[i][j]             else:                 if j == 0 :                     dp[i][j] = dp[i - 1][j] + triangle[i][j]                 elif j == len(dp[i])-1:                     dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]                 else:                     dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]     return max(dp[n-1]) print(int_triangle())