11066번 파일 합치기 문제와 매우 동일하므로 따로 풀이를 적지는 않도록 하겠다. 간단히하자면 DP[i][j] => i번째부터 j번째까지를 계산할때의 최소 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net #include #define INF 1234567890 using namespace std; typedef long long int ll; pair arr[567]; ll dp[567][567] = {0}; int f(int s..
DP문제 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net dp[i][j]를 i번째 수부터 j번째 수까지 붙여 만든 문자열이 팰린드롬인가? (1 or 0) 으로 정의해주면 된다 일단 i와 j가 같은 경우에는 항상 팰린드롬일 것이고, 길이가 짝수인 팰린드롬은 i+1 와 j 번째 숫자가 같아야 한다. 이것들을 먼저 처리해 큐에 넣어주고 BFS를 통해 순회해주며 DP배열을 채우면 된다. #include using namespace std; int dp[2345][2345] = {0}; //..
DP + DFS https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net dp[x][y] 를 (x,y)에서 판다가 먹기 시작할때 지날수 있는 위치의 최대값으로 만들어주면 쉽게 해결할 수 있다. 이 dp[x][y]를 구하기 위해서는 주변 네칸을 탐색 후 dp[nx][ny]가 구해지지 않았다면 이 또한 구해주는 DFS를 이용하면 AC를 받을 수 있다. #include using namespace std; int dx[] = {-1, 1, 0, 0..
약간의 두뇌가 가미된 배낭문제 기본적인 구조는 12865번 평범한 배낭과 동일하다. www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 먼저 딱 보고 생각한 것은 O(KNM)인데, 이렇게 되면 당연하겠지만 TLE가 나온다. O(KNM)은 N개의 물건에 대해서 1~K갯수가 있을텐데, 각각의 개수를 모두 "K배 더 무겁고 K배 가치가 더 나가는 물건" 으로 바꿔주면 쉽게 나온다. AC는 O(NlogKM) 으로 받았는데, K를..
말 그대로 평범한 배낭 문제... www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 0/1 배낭 문제이다. dp[i][j] 를 i번째까지 살펴본 배낭의 용량이 j일때의 최대 가치 로 정의하면 풀수 있다. 이 최대 가치를 만드는법은 크게 세가지 경우로 나뉘는데 1) 배낭에 i번째를 넣을수 있고, 넣었음. ( dp[i][j] = dp[i-1][j-w[i]] + v[i] ) 2) 배낭에 i번째를 넣을..
정올문제의 연속. 일단 디피를 짜는것까지는 좀 빨라진거같아 다행이다. 괄호 문자열은 더하거나 아니면 감싸주는 방식으로 만들 수 있는데, 이는 디피의 특성인 작은 정답이 모여 큰 정답을 만들 수 있다는것과 같다. 문자열을 K로 두고 string dp[i]를 val(K) = i인 문자열 중 dmap(K)의 최소값을 저장한다. 여기서 dmap(K)가 롱롱인트범위를 벗어날 수도 있을거같다는 생각에 혹시몰라서 문자열형으로 만들어줬고, 그렇기때문에 문자열 두개를 비교하는 string cmp함수를 만들었다 문자열을 숫자로 볼때 더 작은 값을 가지는 문자열을 반환해준다. string convert(string s)는 dp배열에서 저장하는 값이 dmap()일때, 이 dmap()의 반환값 형식으로 저장된 값을 다시 괄호 ..