반응형 dp3 [백준] [DP] 가장 긴 바이토닉 부분 수열 11054 (파이썬) 스케치 코드 최장 증가 부분수열 (LIS)에 대한 이해가 필요하다. # 가장 긴 바이토닉 부분 수열 # LIS 문제 n = int(input()) arr =list(map(int,input().split())) dpH = [1 for _ in range(n)] # 증가하는 부분 dpL = [1 for _ in range(n)] # 감소하는 부분 for i in range(n): for j in range(i): if arr[i] > arr[j]: dpH[i] = max(dpH[i], dpH[j]+1) arr.reverse() # 가장 긴수열을 용이하게 구하기 위해서 뒤집니다. for i in range(n): for j in range(i): if arr[i] > arr[j]: dpL[i] = max(d.. 2021. 3. 16. [백준] [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 다음 반응형
