다이나믹 프로그래밍

11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 근우가 왼쪽/오른쪽을 선택했을 때 명우가 선택할 카드의 합이 최소가 되어야 한다. 맨 왼쪽/오른쪽 카드의 수만 비교해서는 최선의 선택이 되지 않기 때문에 다이나믹 프로그래밍으로 접근해야 한다. 여기서 주의할 점은 근우와 명우의 차례에 따라서 구하는 식이 다르기 때문에 2차원 배열을 사용해야 한다. 근우와 명우가 카드를 선택하다가 남은 카드의 상태를 점화식을 세우고, dp [i][j] = i~j의 카드가 있을 때 근우가 선택할 수 있는 최대 합을 만들어야 한다. n이 ..

17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net 17845번 DP문제 중에 knapsack 문제로 해결해야 합니다. bag[M][N]을 1부터 M+1번째 과목들을 대상으로 최대 N시간을 써서 얻을 수 있는 가장 큰 중요도를 구해야 합니다. 현재 i번째 시간으로 들을 수 있을 경우 이전 과목을 들은 경우와 현재 i번째 시간 전 + 현재 i번째 우선도를 비교해서 최대 값으로 bag [i][j]를 갱신해줘야 합니다. 현재 i번째 시간으로 듣지 못할 경우는 이..

풀이과정 해당 문제는 뭔가 일단 규칙성을 찾아야 하게끔 생겨 버렸다. 😶‍🌫️😶‍🌫️ 일단 n이 홀수이면 0인 거 알겠지만, n이 짝수일 때 규칙성을 찾는데 애를 먹었다. 일단 n이 2일 때는 3이다. 그다음 n이 4일 때는 11이다. 근데 여기서 n이 2일 때 경우의 수 각각 2,2이기 때문에 2 * 2에 새로운 모양 2개를 더해준 값이다. 그렇다면 일단 dp [2] * dp [2] + 2라고 표현할 수 있다. 그다음 n이 6일 때는 41이다. dp [4] * dp [2] + dp [2] * 2 + 2 그다음 n이 8일 때는 dp [6] * dp [2] + (dp [4] + dp [2] ) * 2 + 2 그다음 n이 10일 때는 dp [8] * dp [2] + (dp [6] + dp [4] + dp [..

2×n 타일링 2 성공 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 256 MB 23330 13937 11148 59.727% 문제 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. #include int main(void) { int input = 0; scanf("%d",&input); int DP[1001] = {0,}; DP[0] = 1; DP[1] = 1; for(int i=2;i