간단한 DP. 그런데 N범위가 작아서 브루트포스해도 될거같다. dp[k]를 k번째 수를 곱할때의 최대값 으로 정한다. 그러면 dp[k]를 만들 수 있는 방법은 기존까지의 수들을 싹 버리고 k번째 수만을 가지고 새로 시작하는 경우이거나, 기존까지의 수들 = dp[k-1] 에 k번째 수를 곱하는 경우 두가지로 나뉘게 된다. 이렇게 짜주면 쉽게 AC를 받을 수 있다. #include double arr[12345] = {0.0}; double dp[12345] = {0.0}; double max(double a, double b){return a>b?a:b;} int main(){ int n; double ans = -1; scanf("%d", &n); for(int i=0; i

킹격자 갓라기 솔직히 이게 어떻게 플래3일수가 있는거지 ㅠㅠ 환형으로 입력이 주어지는데 케이스를 4가지로 나눠 생각하면 일단 입력을 2차원으로 만들 수 있다. ( 위의 사진 기준 ) 1. 그 어느것도 서로 이어지지 않음. 2. 16번과 9번이 연결 3. 8번과 1번이 서로 연결 4. 16&9, 8&1이 서로 연결 이렇게 네번 계산해서 최솟값을 구해주면 되고, 이제 진짜인 DP파트다 일단 이게 디피라는건 알았으니, 디피를 해보고자 하는데 원래는 디피테이블을 dp[i][j]는 (i,j)를 출동시킬때 라고 생각하였으나 너무 복잡해 수정했다. 디피용 배열을 세개를 만드는데, inner[k] 는 안쪽 k번이 튀어나와있는 형태로 특수소대가 배치되어있는 경우, outer[k] 는 바깥쪽 k번이 튀어나와있는 형태로 특..

처음으로 메모리 초과가 나온 문제. 이제부턴 메모리도 신경써서 풀어야겠다. ​ https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 처음에는 배열을 maxdp를 50만정도, mindp를 50만, 입력도 50만으로 엄청많이 만들어서 메모리 초과가 나왔으나, 어디선가 들었던 기법을 통해 메모리를 대폭 절감해 통과할 수 있었던 문제이다. #include #define MIN(a, b) (((a) < (b)) ? (a) : (b)) #define MAX(a, b) (((..

2차원 배열에서의 Dp는 너무 어려운 거 같다 ㅠ 익숙해질때까지 많이 풀어봐야겠다.... ​ https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 문제 풀때에 있어 굉장히 어려운 부분이 한군데 있었다. ​ 5 5 10 25 7 8 13 68 24 -78 63 32 12 -69 100 -29 -25 -16 -22 -57 -33 99 7 -76 -11 77 15 ​ 테스트케이스에 입력이 이렇게 들어오는데 두번째 줄 첫번째 입력인 68의 경우 단..

무난한 dp 문제였다 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net dp문제를 쬐끔 풀어보면서 느낀게 있다면, 입력배열에서 모든걸 처리하려면 골치아프다는것이다. 그냥 dp배열 하나 더 만들자 ㅎㅎ #include int input[100001] = {0}; int dp[100001] = {0}; int max(int a, int b){ return a>b?a:b; } int main(){ int n,value = -1234; scanf("%d", &n)..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net #include int dp[10005] = {0}; int arr[10005] = {0}; int max(int a, int b){ return a>b?a:b; } int main(){ int n; scanf("%d", &n); for(int i=3; i

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 배열을 어떻게 만들어야 할지 고민했던 문제. dp배열을 만든 뒤로는 그냥 무난하게 풀어냈다. #include int dp[1001][3] = {0}; int min(int a, int b){ return a>b?b:a; } int index(int k){ if(k==3){return 0;} if(k==-1){return 2;} return k; } int main(){ int..

2차원 DP 를 통해 풀어줄 수 있다. www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net dp[a][b]는 완벽한 상태의 알약이 a개, 반개짜리 알약이 b개일때의 문자열의 개수이다. 완벽한 알약을 하나 복용하고 반개짜리 알약으로 만들어 줄 수 있으므로, dp[a-1][b+1]의 경우가 생길 수 있고, 반개짜리 알약이 있는 경우 ( b > 0 ) 에는 반개짜리를 먹는 경우도 추가로 더해준다. 굳이 a==0 && b==0일때 탈출하지 않는 이유는 어차피 dp[a][k]에서 a가 ..