WoohyunKing의 개발 성장일지

11659번: 구간 합 구하기 4첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 jwww.acmicpc.netn,m = map(int,input().split())numbers = list(map(int,input().split()))answers = []dp = [0]*(n+1)for i in range(1,n+1): dp[i] = dp[i-1] + numbers[i-1]for _ in range(m): i, j = map(int,input().split()) answers.append(dp[j]-dp[i-1])for answer in..

이번 문제는 연속으로 3칸을 밟을 수 없고 한번에 1칸이나 2칸씩 계단을 오를 수 있다는 가정 하에, 마지막 도착 계단까지 도착하는데 얻을 수 있는 총 점수의 최댓값을 구하는 문제이다. 먼저 이 문제는 완전탐색으로 풀 경우에는 N이 최대 300이기 때문에 2^300 의 경우의 수로 인해 시간초과가 발생하게 된다. 따라서 O(n) 시간복잡도로 풀 수 있는 DP 알고리즘을 사용해야 한다. 처음에 이 문제를 풀이했을 때는 dp 테이블을 1차원 배열로 선언해서 점화식을 도출하려고 했었는데, 1차원으로 선언하게 되면 점화식을 세우고 싶어도 연속한 세 계단을 모두 밟아서는 안 된다는 제약 조건을 점화식에 넣을 방법이 없다.(연속해서 몇 개의 계단을 밟았는지 확인할 수 없음) 따라서 i번째 계단까지 밟았을 때의 총 ..