dp

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

풀이과정 해당 문제는 뭔가 일단 규칙성을 찾아야 하게끔 생겨 버렸다. 😶‍🌫️😶‍🌫️ 일단 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 [..

2176번: 합리적인 이동경로 첫째 줄에 정점의 개수 N(1 < N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 100,000이 주어진다. 다음 M개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 길이 www.acmicpc.net 풀이 과정 DP를 최단 경로를 탐색하기 위하여 사용된다. dp의 i번째 인덱스는 출발하는 합리적인 이동경로의 수를 의미하며, 도착점 2번 노드부터 탐색을 시작한다. 각 정점까지의 최단경로를 갱신하는 과정에서 현재 노드까지 최단 경로의 길이가 다음 노드까지 최단 경로의 길이보다 짧을 경우, 다음 노드와 현재 노드 사이에 합리적인 이동 경로가 존재한다는 뜻이다. 풀이 과정 import sys,heapq; input =..

5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 과정 1. n이 100개라고 브루트 포스로 풀면 안 된다.. 100개의 데이터가 나올 경우, 나올 수 있는 가지 수가 2^99가 나온다. 이 문제는 dp문제로 문제에서 주어진 0보다 크거나 같고 20보다 작거나 같은 조건을 이용해서 해결해야 한다. 2. dp의 크기를 21으로 할당해준다. 그리고 주어진 배열(arr)의 첫 번째 인덱스의 값을 dp의 인덱스에 1로 설정한다. 첫 번째 숫자는 반드시 포함되어야 하기 때문에!! 3. 이중 반복문을 사용하였..

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 코드 #include #include using namespace std; int T,N; int main(void) { for(cin >> T; T>0; T--) { cin >> N; vector dp(N); dp[0] = 1; dp[1] = 2; dp[2] = 4; for(int i=3; i

코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 문제 설명 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 re..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 코드 #include #include #include using namespace std; int n; int main(void) { cin >> n; vector v(n+1,0); for(long long i=2; i

문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 코드 #include #include using namespace std; int main(void) { int n; cin >> n; vector dp(n+1); dp[0] = 0; dp[1] = 1; dp[2] = 1;..