[Python] 백준 16395번: 파스칼의 삼각형
https://www.acmicpc.net/problem/16395 [풀이]기존 연산이 다음 연산에 영향을 미치기 때문에 DP로 풀이했다.우선 대각선 형태로 되어 있는 것을 N*N 형태의 배열로 만들었다. 또한, 초기값을 1로 만들고 나서 다음 연산할 부분만 2중 for문으로 만들어서 파스칼의 삼각형을 완성했다. [코드]n, k = map(int, input().split())dp = [[1] * (n + 1) for _ in range(n + 1)]for i in range(3, n + 1): for j in range(2, i): dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]print(dp[n][k]) [시간복잡도]O(N^2)
CS/Algorithm
2025. 6. 2.
![[Python] 백준 16395번: 파스칼의 삼각형](http://i1.daumcdn.net/thumb/C400x400/?fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdna%2FR6xhh%2FbtsOm9H4gfJ%2FAAAAAAAAAAAAAAAAAAAAAI8o-AtCLbxTMvwm5Y9CcDdV0jbsYRxAP-YojJR_ZRS2%2Fimg.jpg%3Fcredential%3DyqXZFxpELC7KVnFOS48ylbz2pIh7yKj8%26expires%3D1753973999%26allow_ip%3D%26allow_referer%3D%26signature%3DTlKV%252F39x4Dfed0AzN3Qa0QGuZ2k%253D)