코딩 테스트/다이나믹 프로그래밍11 [백준 10844번] 쉬운 계단 수 문제풀이 (with Python) dp 배열을 2차원 리스트로 정의해서, 자리수에 대한 정보를 dp에 넣는 새로운 문제였다. 감이 잘 잡히지 않아 소스를 참고해서 풀었다. dp[자리수][앞 자리의 수] 값은 가능한 경우의 수이다. 1) 앞 자리가 0인 경우, dp[ i ][ j ] = dp[ i - 1 ][ 1 ] 2) 앞 자리가 1~8인 경우, dp[ i ][ j ] = dp[ i -1 ][ j -1] + dp[ i -1 ][ j +1] 3) 앞 자리가 9인 경우, dp[ i ][ j ] = dp[ i -1 ][ 8 ] N = int(input()) dp = [[0]*10 for _ in range(N+1)] for i in range(1, 10): dp[1][i] = 1 for i .. 2023. 8. 23. [백준 11722번] 가장 긴 감소하는 부분 수열 문제 풀이 with Python 각 인덱스 별로 앞의 수보다 다음 수가 작을 경우 1씩 올려준다. dp를 이용하여 dp[i]에 인덱스 i까지 가장 긴 감소하는 부분 수열의 길이를 저장한다. n = int(input()) arr = list(map(int, input().split())) dp = [1 for i in range(n)] for i in range(n): for j in range(i): if arr[j] > arr[i]: dp[i] = max(dp[i],dp[j]+1) print(max(dp)) 2023. 8. 22. [백준 11049번] 행렬 곱셈 순서 문제 풀이 주어진 행렬의 최소 곱셈 연산을 구하는 문제이다. dp를 이용해서, dp[i][j]에 i+1번째 행렬부터, j+1번째 행렬까지 곱했을 때의 곱셈 연산 횟수의 최솟값을 저장해서 풀었다. N = int(input()) arr = [] INF = int(1e9) for _ in range(N): r, c = map(int, input().split()) arr.append((r, c)) dp = [[0] * N for _ in range(N)] for i in range(N - 1): dp[i][i + 1] = arr[i][0] * arr[i + 1][0] * arr[i + 1][1] for L in range(2, N): i = 0 j = L while j.. 2023. 8. 21. [백준 2579번] 계단 오르기 문제 풀이 1. 계단이 1, 2개 일때는 모두 더한 값이 최대 값이다. 2. 계단이 3개 이상일 때는 현재 계단을 k (k>=3)번 이라 할때, (price[k] + price[k-2])와 price[k] + price[k-1] + price[k-3]) 의 값을 비교하여 최댓값을 저장해주어야 한다. n = int(input()) s = [int(input()) for _ in range(n)] # 각 계단의 점수 리스트 max_score = [0] * (n) if len(s) 2023. 8. 2. 이전 1 2 3 다음
