코드 #include #include #define DIV using namespace std; int arr[101][101]; long long dp[101][101]; #define DIV 1000000007 int solution(int m, int n, vector puddles) { int answer = 0; // 물 표시 for (int i = 0;i < puddles.size();i++) { int x = puddles[i][0], y = puddles[i][1]; arr[y - 1][x - 1] = -1; dp[y - 1][x - 1] = 0; } if (arr[0][0] != -1) { dp[0][0] = 1; } for (int i = 1;i < n;i++) { if (arr[i][..

문제 남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다. 이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다. 돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는? 제약조건 1 ≤ N ≤ 3×103 인 정수 1 ≤ Ai ≤ 108 인 정수 입력형식 첫 번째 줄에 돌의 개수 N이 주어진다. 두 번째 줄에 돌의 높이 Ai (1 ≤ i ≤ N)가 서쪽부터 동쪽으로 차례로 주어진다. 출력형식 첫 번째 줄에 철수가 밟을 수 있는 돌의 최대 개수를 출력하라. 풀이방법 이 문제는 전형적인 dp 문제이다. dp 문제를 정말 오랜만에 풀어보는 것 같다. dp[n] = n번째 까지 오름차순으..

1. 문제 문제는 다음과 같다. 2. 풀이법 문제 분류는 dp이나 적당히 수의 특성을 살펴보면 쉽게 문제를 해결할 수 있다. 어떤 수를 멱수의 합으로 나타낼 수 있는 방법은 두가지이다. 1. 그 전수에서 1(2^0)을 더한다. 2. 1이 아닌 멱수로만 수를 표현한다. 즉, 수의 합을 "1이 포함된 집합"과 "1이 포함되지 않은 집합"으로 나누는 것이다. 홀수의 경우, (1)으로만 풀이가 가능하다. 전 수의 멱수의 합에서 1을 더하는 것을 제외하고 다른 방법으로 합을 표현할 수 있는 방법이 존재하지 않는다. 짝수의 경우, 그 전수에서 1을 더하는 경우와, 그 수를 2로 나눈 값의 경우의 수를 더하면 답을 구할 수 있다. 해당하는 짝수를 n이라고 하자. n/2를 표현하는 수가 x+y라고 했을 때, 2(x+y..