Dynamic programming

문제 분석 과정 주어진 조각은 3개이고, 회전은 불가능하다 마지막 칸(가장 우측)을 바라 보자 그러면 가능한 마지막칸을 구성하기 위한 case를 나눌 수 있다. > 1x1을 2개를 구성해서 2x1칸을 이루는 경우 => (2,1) 2x1 1개로 2x1칸을 이루는 경우

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비

다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:t(0)=1t(n)=t(0)t(n-1)+t(1)t(n-2)+...+t(n-1)\*t(0)이 정의에 따르면,t(1)=t(0)t(0)=1t(2)=t(0)t(1)+t(1)t(0)=2t(3)=t(0)t(2)+t(1)t(1)

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수

45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

문제를 분석하는 과정에서 시행착오가 있었다. 첫 시도는 데이터를 튜플형태로 받은 후 각 인덱스 마다 교차하는 갯수를 구하였다. 그리고 2차원 dp 테이블을 활용하여 dp 테이블을 초기화 시켜간후,교차하는 갯수가 0일 때 활성화된 인덱스가 최소인 것을 찾으려했다.교차함을