김머성 블로그

[BAE/<JOON> 문제풀이] 2410. 2의 멱수의 합

https://www.acmicpc.net/problem/2410 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 실버 문제가 다 쓰기 전에 골드 12라인 못뚫을것 같다. 실버 문제 4개밖에 안남았다... 더보기 #include #include #include using namespace std; int main() { int n; cin >> n; vector coin; vector dp; int ct = 1; while (ct

[BAE/<JOON> 문제풀이] 7579. 앱

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활�� www.acmicpc.net 가방(갯수제한 문제) 더보기 #define _CRT_SECURE_NO_WARNINGS #include #include #include //0/1 knapsack prob using namespace std; int main() { int n, m; cin >> n >> m; vector w; vector cost; vector dp; w.resize(n + 1); cost.resize(n + 1); ..

[BAE/<JOON> 문제풀이] 10835. 카드게임

https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오�� www.acmicpc.net 처음에 일반적인 n*n 포문으로 점화식 짜서 풀었다. 근데 자꾸 틀려서 코너케이스 찾다가 포기하고 답봤는데 바텀업 재귀 써서 푸는 문제였다. 답보고 생각해보니까 각 단계에 대해서 이전 단계는 (-1, -1)과 (-1, 0), (0, -1) + right[0] 세가지이므로 바텀업 재귀가 맞는 풀이였다. 왜 n*n포문으로 했는지 나도 모르겠다. 심지어 그렇게 푼 코드 코..

[BAE/<JOON> 문제풀이] 9184. 신나는 함수실행

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 문제 재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b a www.acmicpc.net 지금은 앞에 있는 쉬운 문제 먼저푸는 방식으로 때우고는 있는데 문제들이 점점 어려워져서 이제 하루 1문제 못할 수도 있을 것 같다. 더보기 #include using namespace std; int dp[51][51][51]; int w(int a, int b, int c) { if (a 20) return dp[a][b][c] = w(20, 20, 20); if(a < b &..

[BAE/<JOON> 문제풀이] 5582. 공통 부분 문자열

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예 www.acmicpc.net LCS 문제인줄 알고 풀었는데 연속된 문자열만 인정하는 문제였다. LCS 하위호환 문제같다. 더보기 #include #include #include #include using namespace std; int dp[4001][4001]; int main() { string s1, s2; cin >> s1 >> s2; int l1 = s1.length(); int l2 = s2.lengt..

[BAE/<JOON> 문제풀이] 1958. LCS3

https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다) www.acmicpc.net LCS(LCS(A, B), C)와 LSC(A, B, C)가 다르다는걸 알아야 한다. LCS는 항상 최장 공통 문자열만 찾기 때문에 다음과 같은 반례가 생겨난다. s1 = asdfasdfmeo s2 = asdfasmeo s3 = kimmeoseong s1과 s2를 연산하면 asdfas가 검출되므로 마지막의 s3와의 LCS를 구하면 0이 나온다. 그래서 3차원 배열로 다시 짰다. 다행히도 공통문자열을 출력하는 문제는 아니라서 2개 문자열 구하는..