해킹왕 양선규

누적 합, DP 문제이다.2차원 리스트를 사용하기 때문에 단일 리스트보단 조금 더 복잡하다. # 실버1 -> 누적 합"""N : 표의 크기M : 합을 구해야 하는 횟수"""import sysinput = sys.stdin.readlineN, M = map(int, input().split())origin = [list(map(int, input().split())) for _ in range(N)]# dp(누적 합)테이블 생성dp = [[0] * (N + 1) for _ in range(N + 1)]for i in range(1, N + 1):    for j in range(1, N + 1):        dp[i][j] = origin[i-1][j-1] + dp[i][j-1] + dp[i-1][j] ..

DP 문제이다. 언제나 어렵고 새롭고 가장 싫어하는 알고리즘이다. # 실버1 -> DPimport sysinput = sys.stdin.readline# 테스트 케이스 개수T = int(input())for _ in range(T):    N = int(input()) # 스티커 길이    sticker = []    sticker.append(list(map(int, input().split())))    sticker.append(list(map(int, input().split())))    if N == 1:        print(max(sticker[0][0], sticker[1][0]))        continue    dp = [[0] * (N + 1) for _ in range(3)] ..

끔찍한 DP 문제이다.문제를 고른 후에 알았는데 꽤 유명한 문제인 것 같다.말 그대로 계단 수의 개수를 구하는 문제다. 점화식을 찾으면 쉽게 풀 수 있지만 그것을 찾는 게 매우 어렵다. 처음 접근 방식은, 1, 2, 3 자리수 계단 수 개수를 세서 그 증가폭에 대한 규칙을 찾으려 했지만 실패했다. 이 문제를 쉽게 풀기 위해선 2차원 배열을 사용하는 것과, 끝나는 숫자를 기준으로 생각하면 좀 더 쉽다. 예를 들어, N번째 자리에 숫자 1이 오기 위해선 N-1번째 숫자가 반드시 0 또는 2여야 한다.즉, N-1번째에서 0으로 끝나는 숫자의 수와 2로 끝나는 숫자의 수를 합하면 N번째 자리에 1이 오는 계단수의 개수를 알 수가 있다. 표를 그려보면 좀 더 이해하기 쉽다.  행은 자릿수(N), 열은 끝나는 수이..