동적 프로그램 (4) 썸네일형 리스트형 [백준] 12865번 평범한 배낭 [Python] - 다이나믹 N개의 물건과 각 물건의 무게 W, 가치 V가 주어질 때, 최대 무게 K 내에서 가치의 합이 최대가 되는 그 최댓값을 구하는 문제 더보기 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의.. [백준] 9251번 LCS [Python] - 다이나믹, 문자열 LCS$($Longest Common Subsequence, 최장 공통 부분 수열$)$문제 최장 공통 부분 수열 더보기 문제 LCS$($Longest Common Subsequence, 최장 공통 부분 수열$)$문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. https://www.acmicpc.net/problem/9251 한 단어의 철자를 순서대로 다른 단어의 철자와 비교하면서 같은 철자가.. [백준] 2096번 내려가기 [Python] - 다이나믹 N행 3열에 0 이상 9 이하의 숫자가 적혀 있다. 첫번째 줄부터 내려가면서 숫자를 하나씩 선택해서 총 N개의 숫자를 모두 더하면 점수가 된다. 아래 그림처럼 현재 선택 된 곳이 ☆이면 그 아래 줄에서 바로 아래거나 그 옆인 곳만 선택할 수 있다. 위 조건을 만족하면서 최대/ 최소 점수를 구하는 문제이다. 더보기 문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이.. [백준] 25706번 자전거 묘기 [Python] - 다이나믹 자전거를 타고 점프대를 지나면 그 높이만큼 칸을 건너 뛴다. 1번칸부터 N번칸 까지 자전거를 타고 출발할 때, 지나가게 되는 칸의 수를 구하는 문제 더보기 문제 길이가 N미터인 직선 자전거 도로가 있다. 도로는 길이가 1미터인 N개의 칸으로 구분되어 있고, 가장 왼쪽에 있는 칸부터 순서대로 1번 칸, 2번 칸, …, N번 칸이다. 도로의 각 칸에는 점프대가 설치되어 있을 수 있다. i$($1 ≤ i ≤ N$)$번 칸에 설치된 점프대의 높이를 hi라고 하자. 높이가 hi인 점프대를 밟으면 그 어떤 요인과도 관계없이 다음 hi칸 위를 비행한 뒤 그다음 칸에 착지한다. 다음 예시를 확인해 보자. 자전거를 타고 1번 칸에서 출발해 앞으로 달리면 다음과 같은 일들이 순서대로 일어난다. 1번 칸에 점프대가 없으므로.. 이전 1 다음
