너와 나의 스토리

문제: https://www.acmicpc.net/problem/1890 문제풀이: "경로의 개수는 2^63-1보다 작거나 같다." -> long long "메모리 제한: 128 MB" -> DP 이미 갔던 길 다시 안가고 그 지점에서 갈 수 있는 경우의 수+1 해주면 됨 * 함수 리턴 타입 확인 잘하자.... int func()해서 계속 틀림 ㅠㅅㅠ 소스코드: int n, arr[100][100]; long long dp[100][100]; long long func(int x, int y) { if (x == n - 1 && y == n - 1) return 1; if (x >= n || y >= n) return 0; long long& ret = dp[x][y]; if (ret != -1) ret..

문제: https://www.acmicpc.net/problem/11722 문제 풀이: https://hororolol.tistory.com/103 (BOJ) 11053 가장 긴 증가하는 부분수열 문제: https://www.acmicpc.net/problem/11053 문제풀이: 현재 위치 이전에 자기보다 작은 값 찾아서, 작은 녀석까지의 최대 개수+1 소스 코드: int n,arr[1001],dp[1001],res; int main() { ios::sync_with_stdio.. hororolol.tistory.com ㄴ 거의 같은 문제 부등호 방향만 바꾸면 됨 소스코드: 풀이1 - 시간 복잡도: O($n^{2}$) int n,arr[1001],dp[1001],res; int main() { ios:..

문제: https://www.acmicpc.net/problem/11053 문제풀이: 현재 위치 이전에 자기보다 작은 값 찾아서, 작은 녀석까지의 최대 개수+1 소스 코드: 시간복잡도: O($n^{2}$) int n,arr[1001],dp[1001],res; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n; for (int i = 0; i > arr[i]; dp[i] = 1; for (int j = 0; j < i; j++) { if (arr[j] < arr[i]) { dp[i] = max(dp[i], dp[j] + 1); } } res = max(res, dp[i]); } c..

문제: https://www.acmicpc.net/problem/9251 문제풀이: ex) ACAYKP CAPCAK A C A Y K P 0 0 0 0 0 0 0 C 0 0 1 1 1 1 1 A 0 1 1 2 2 2 2 P 0 1 1 1 2 2 3 C 0 1 2 2 2 2 2 A 0 1 2 3 3 3 3 K 0 1 2 3 3 4 4 => 답: 4 행과 열의 첫 줄을 0으로 해둠 같은 문자를 만나면 대각선, 즉, 현재 (x,y)라면 (x-1,y-1) 값 +1 해준다 // arr[x][y]=arr[x-1][y-1]+1; 다른 문자를 만다면 자신의 왼쪽이나 위쪽 값 중 큰 값을 넣어줌 // arr[x][y]=max(arr[x][y-1],arr[x-1][y]); 가장 큰 값이 결과값이다. 소스 코드: strin..

for문을 이용한 방식 int n, dp[1000001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n; for (int i = 2; i n; memset(dp, -1, sizeof(dp)); cout