해킹왕 양선규

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

import sysinput = sys.stdin.readlineN = int(input())def plus(num):    if num == 1:        return 1    elif num == 2:        return 2    elif num == 3:        return 4    else:        return plus(num-1) + plus(num-2) + plus(num-3)for _ in range(N):    print(plus(int(input()))) 재귀 방식( 바람직하지 않음 ) DP문제다. 두가지 방식으로 풀어보았다. 하나는 재귀 방식, 하나는 DP테이블을 사용하는 방식.이해를 하긴 했으나 뭔가 와닿지가 않는다. 아 이런거구나~ 하고 이해해놓고 잠시 뒤에, 근..

import copyimport sysinput = sys.stdin.readlineN = int(input())numList = list(map(int, input().split()))dp = copy.deepcopy(numList)for i in range(1, N):    for j in range(i):        if numList[i] > numList[j]:            dp[i] = max(dp[i], dp[j] + numList[i])print(max(dp)) 가장 긴 증가하는 부분 수열(LIS)문제와 거의 흡사한 문제이다. 문제의 원리는 거의 같지만 요구하는 출력값이 다르다. LIS는 수열이 길이를 출력했다면, 이 문제는 수열을 모두 더한 값을 출력한다. dp테이블로 사용하기 ..

import sysinput = sys.stdin.readlineN = int(input())numList = list(map(int, input().split()))dp = [1] * Nfor i in range(1, N):    for j in range(i):        if numList[i] > numList[j]:            dp[i] = max(dp[i], dp[j]+1)print(max(dp)) Longest Increasing Subsequence(LIS) 문제로, DP유형의 대표적인 문제 중 하나다.처음엔 문제만 보고 뭐야 이게 진짜 실버2라고..? 란 생각과 함께 코드를 짜서 제출했지만 역시 실패했다. 나는 크게 두 가지를 간과했다.1. 수열이 첫 번째 숫자부터 시작할 필요..

# 1일차의 최댓값, 2일차의 최댓값, 3일차의 최댓값.. 순으로 N일차의 최댓값까지 구한다import sysinput = sys.stdin.readline#  상담 가능 일수N = int(input())# 시간과 수익을 따로 입력받는다time, point = [0 for _ in range(N + 1)], [0 for _ in range(N + 1)]for i in range(1, N + 1):    time[i], point[i] = map(int, input().split())# dp 테이블 만들고, 1일부터 로직 시작dp = [0 for _ in range(N + 1)]for i in range(1, N + 1):    # 기존에 있던 값과 전날 값을 비교해 큰 값으..

import sys N, K = map(int, input().split()) # 물건 수, 버틸 수 있는 무게 item = [[]] # 물건 입력받기 (무게, 가치) for _ in range(N): item.append(list(map(int, input().split()))) dp = [[0 for _ in range(N + 1)] for _ in range(K + 1)] # dp테이블 만들기, 0행과 0열은 0으로 채우기 for x in range(1, K + 1): for y in range(1, N + 1): if x - item[y][0] >= 0: # 현재무게 - 현재물건무게 값이 0이상이라면 (dp테이블에 있다면, 담을 수 있다면) dp[x][y] = max(dp[x][y-1], dp[x..

a = [[]] # dp테이블과 인덱스를 동기화하기 위해 빈 리스트를 추가한다. b = [[]] for i in list(input()): a.append(i) for i in list(input()): b.append(i) # 0행과 0열 값을 모두 0으로 맞춰준다. # 첫번째 비교부터 공식을 적용하려면 이전 값이 존재해야 하기 때문에 맞춰주는 것. dp = [[0 for _ in range(len(a))] for _ in range(len(b))] for x in range(1, len(b)): for y in range(1, len(a)): if b[x] == a[y] : # 문자열이 일치할 경우 dp[x][y] = dp[x-1][y-1] + 1 # 좌측위 방향 값에서 +1 더한 값 else: # ..

import sys input = sys.stdin.readline T = int(input()) # 테스트 케이스 개수 for _ in range(T): # 테스트 케이스 개수만큼 진행한다 N = int(input()) # 동전 종류 개수 coinBox = list(map(int, input().split())) # 동전 입력받기 coinBox.insert(0, 0) # 0번 인덱스에 0넣기. 첫번째 동전부터 점화식을 적용하기 위함. money = int(input()) dp = [[0] * (money + 1) for i in range(N + 1)] # 목표금액만큼 한 행을 길게, 동전갯수만큼 한 열을 길게 for i in range(N + 1): dp[i][0] = 1 # 동전이 뭐든 간에 0을 ..

x = int(input()) d = [0] * (x + 2) d[1] = 1 d[2] = 2 for i in range(3, x + 1): d[i] = (d[i-1] + d[i-2]) % 15746 print(d[x]) 다이나믹 프로그래밍 문제이다. 점화식만 찾으면 아주 간단하게 해결할 수 있다. 계산값을 저장해둘 DP테이블(리스트 d)를 생성하고, 초기값을 넣어준다. d[1]엔 1길이의 수열에서 나올 수 있는 경우의 수의 개수, d[2]엔 2길이, d[x]엔 x길이의 수열에서 나올 수 있는 경우의 수의 개수가 들어간다. 타일 경우의 수를 구하는 것은 언뜻 답이 없어 보이지만, 규칙이 있다. 현재 값들에 1을 붙이고, 이전 값들에 00을 붙이면 그게 다음 값이 된다. 즉 N=4 일 때의 경우의 수를 구..

x = int(input()) d = [0] * (x + 2) d[1] = 1 d[2] = 1 for i in range(3, x + 1): d[i] = d[i-1] + d[i-2] print(d[x]) 간단한 DP 문제이다. 재귀함수로 구현하면 입력값이 90까지이기 때문에 메모리가 터져버린다. x가 1, 2일 경우만 리스트에 등록해 둔 후 간단한 반복문을 돌리면 된다. 재귀 구현했을 경우 90이면 정말 컴퓨터가 터지기 직전까지 가는데 상향식 DP방식인 반복문으로 구현하면 대략 90번정도만 연산하면 되기 때문에 문제를 해결할 수 있다.