반응형 동적계획법2 [백준] [DP] 계단오르기 2579 (파이썬) 문제설명 dp 테이블을 무엇으로 설정할지 정하여 점화식을 구하는 것이 관건인데 스스로 풀지 못하였다. 잘못접근 한뒤로 구글링 해서 올바르게 접근하였다. 스케치 코드 # 계단오르기 import sys n = int(sys.stdin.readline().rstrip()) score = [0] # 0 층 점수 0을 넣어주기 for _ in range(n): score.append(int(sys.stdin.readline().rstrip())) # 1층부터 ~ N층까지 점수 넣어주기 dp = [0 for _ in range(n+1)] # 값이 0인 dp 테이블 초기화 dp[0] = score[0] dp[1] = score[1] if n >= 2: #index 오류 안되게 조건 추가 dp[2] = max(scor.. 2021. 3. 15. [백준] [DP] 파도반 수열 9461 (파이썬) 스케치 규칙이 발견되면 dp로 간단하게 해결 할 수 있다. # 9:16 ~ 9:32 # 파도반 수열 T = int(input()) for _ in range(T): n = int(input()) d = [0]* 101 d[1] = 1 d[2] = 1 d[3] = 1 d[4] = 2 d[5] = 2 # 6번째 부터 규칙이 발견 for i in range(6, n+1): d[i] = d[i-1] + d[i-5] print(d[n]) 2021. 3. 14. 이전 1 다음 반응형
