............ ............

#include #include #define MAX 16+1 #define INF 987654321 using namespace std; int N, P; int arr[MAX][MAX]; //dp[x][y] => 현재 y상태에서 발전소 x번에서 시작할때의 최소비용 int dp[MAX][1 = 1; } return cnt; } int func(int idx, int currState) { //currState의 1의 개수가 P-1개 이상 => P개의 발전소켜짐 => 0리턴 //state의 초기값 맨 앞에 1이 기본적으로 추가가되므로 if (count1(currState) -1 >= P) return 0; int &ref = dp[idx][currState]; if (ref != -1) return re..

문제 https://www.acmicpc.net/problem/11062 11062번: 카드 게임 문제 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다. 카드가 더 이상 남아있지 않을 때까지 턴은 반복된다. 게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다. 근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다. 놓여있는 카드의 개수 www.acmicpc.net 목표 두 사람이 나열된 카드중 맨앞 또는 맨뒤 카드만 선택하여 높은 점수를 획득하기위한 게임에서 최고점수를 구하기 풀이 dp로..

문제 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 목표 무작위로 주어진 배열에서 증가하는 부분수열중 가장 긴 수열을 찾는다. 풀이 배열하나를 만들어 값들을 읽어나가면서 그 값이 들어갈 수 있는 위치와 그 값을 새로운 배열에 저장한다. 이렇게 하는 이유는 모든 탐색이 끝난후 해당 수열을 출력할때 알맞은 값을 찾기위함이다. 즉 값이들어갈 위치 인덱스가 섞이더라도, 나중에 출력시 알맞은 인덱스의 값을 출력하기 위함이..

문제 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다. www.acmicpc.net 목표 행렬 연산을 할때 곱셈순서에 따라 값은 변하지 않지만 필요한 곱셈연산의 수는 달라진다. 따라서 주어진 행렬들이있을때 최소 곱셈 연산횟수를 구하라 풀이 ㅈㄴ어려움.. 재귀로 푸는방법과 반복문으로 푸는방법이 있다. 1. 재귀 일단 재귀는 top-down으로 푸는데 점화식은 for (int i=left; i N; for (int i=0; i> arr[i].first >> ar..

문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 목표 0과 1로 이루어진 배열이 주어질때 1로 이루어진 가장 큰 정사각형의 넓이를 출력 풀이 dp를 사용하여 dp배열에 가장 큰 정사각형의 변의 길이를 저장한다. 점화식 dp[i][j] = if ( dp[i][j]==1 && dp[i][j-1]!=0 && dp[i-1][j]!=0 && dp[i-1][j-1]!=0 ) dp[i][j] = min(dp[i][j-1], dp[i-1][j]); dp[i][j] = min(dp[i][j], dp[i-1][j-1]) + 1..

문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 목표 두개의 문자가 주어졌을때 두 문자의 부분수열중 최장길이의 부분수열을 구하는 문제 풀이 dp를 사용하여 각 구간마다 최장부분수열의 길이를 저장시켜놓는다. 사진에서 동그라미 친 부분은 두 문자열의 부분문자가 같은 구간 => dp값이 1증가해야한다. 점화식 dp[i][j] = if (s1[i] == s2[j]) dp[i-1][j-1] + 1; ..

문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. www.acmicpc.net 목표 N개가 주어졌을때 주어지는 구간의 합을 구하기 풀이 시간초과때문에 수를 읽을때마다 누적합을 구하는 배열을 생성함 그후 (n,m)범위가 들어오면 totalSum[m] - totalSum[n-1]연산으로 구간합을 구함 즉 (0~m) 까지의 전체합에서 (0~n-1)까지의 전체합을 빼주면됨 코드..

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 목표 가중치가 쓰인 계단이 있을때 마지막 계단까지 이동하며 얻을수 있는 최대 가중치 구하기(단, 3개연속 불가능) 풀이 점화식: dp[i] = sta..