반응형 알고리즘/dynamic programming27 [백준][Python] 16395번 파스칼의 삼각형 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 코드 n,k = map(int,input().split()) pascal = [[1]*i for i in range(1,31)] if n > 2: for i in range(2,n): for j in range(1,i): pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j] print(pascal[n-1][k-1]) 2022. 12. 26. [백준][Python] 11060번 점프 점프 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 코드 n = int(input()) a = list(map(int,input().split())) dp = [n+1]*n dp[0] = 0 for i in range(n): for j in range(1,a[i]+1): if i + j < n: dp[i+j] = min(dp[i+j],dp[i]+1) if dp[-1] == n+1: print(-1) else: print(dp[-1]) 2022. 12. 23. [백준][Python] 13699번 점화식 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 코드 n = int(input()) t = [0 for _ in range(n+1)] t[0] = 1 for i in range(1,n+1): for j in range(i): t[i] += t[j]*t[i-j-1] print(t[n]) 2022. 12. 19. [백준][Python] 18353번 병사 배치하기 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 코드 n = int(input()) n_list = list(map(int,input().split())) dp = [1 for _ in range(n)] for i in range(1,n): for j in range(0,i): if n_list[i] < n_list[j]: dp[i] = max(dp[i],dp[j]+1) print(n-max(dp)) 2022. 12. 14. 이전 1 2 3 4 5 ··· 7 다음 반응형
