www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 간단한 DP 문제였다. 삼각형이 n = 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 이런 식으로 주어진다면 가장 밑 줄에서 가장 큰 수를 얻으려면 0번째 줄에서 그다음 줄로 현재 값에서 왼쪽으로 내려가던가, 오른쪽으로 내려가던가 이 두 가지 경우의 수만 따져주면 된다. max(solve(x + 1, y + 1), solve(x + 1, y)) + ar[x][y] table[x][y] 의 값은 결국 위의 식처럼 될 것이다. #include #include #include ..

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 슬라이딩 윈도를 사용해서 공간 복잡도를 O(1)로 만들고 풀어야 하는 문제. 라이님의 블로그를 참고해서 풀었다. DP식 짜는 것은 매우 쉽지만 필요 메모리가 무려 4MB이다... DP 식을 잘 보면 cin >> TMX[j]; TMN[j] = TMX[j]; TMX[j] += max(MX[1], (j == 1) ? max(MX[0], MX[2]) : MX[j]); TMN[j] += min(MN[1], (j == 1) ? min(..

www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 정수형 배열을 입력받고 구간의 값이 팰린드롬인지 판단하는 문제다. 처음에는 문자열로 접근해서 reverse를 사용했지만 2000번에 대해서 1백만 번씩 뒤집히니 시간 초과. 결국 dp로 풀었다. #include #include using namespace std; int f(vector& d, vector& ar, int s, int e) { if (s >= e) return 1; if (d[s][e] != -1) return d[s][e]; if ..