처음으로 메모리 초과가 나온 문제. 이제부턴 메모리도 신경써서 풀어야겠다. ​ 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/2553 2553번: 마지막 팩토리얼 수 첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수 이다. www.acmicpc.net #include int f(int k, int t){ if(t == 1) return k; k = k*t; while(k%10 == 0) k/=10; k = k%100000; return f(k, t-1); } int main(){ int n; scanf("%d", &n); printf("%d", f(1, n)%10); } 재귀함수를 이용해서 풀어줬다. k는 계산중인 팩토리얼 수이고, t는 곱해야 할 수이다. ​ t가 1이라면 더 곱해줄 필요가 없으므로 k를 결과값으로 반환해주고, 아닐경우에는 k에 t를 ..

슬슬 바텀업 방식 DP의 감이 잡히는거같기도 하고... 그래도 역시 너무 섣부른거 같긴 하다 아직. ​ https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 그냥 dp배열을 1차원으로 만드려다 0으로 시작하는 수는 없다는 규칙때문에 배열을 2차원으로 짜냈다. #include int dp[101][11] = {0}; int index(int k){ if(k==-1){return 10;} return k; } int main(){ int n,sum=0; scanf("%d", &n); for(int i=1; i

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