-
[BOJ] 9251 : LCS
9251 : LCS 풀이 dp[i][j] = a[1~i]와 b[1~j]의 LCS 값 dp[i][j] = max(d[i-1][j], d[i][j-1], d[i-1][j-1] + (a[i] == b[j])) 코드 #include <stdio.h> #include <algorithm> char a[1111], b[1111]; int i, j, d[1111][1111]; int main() { scanf("%s\n%s", a + 1, b + 1); for (i = 1; a[i]; i++) for (j = 1; b[j]; j++) d[i][j] = std::max({ d[i-1][j], d[i][j-1], d[i-1][j-1] + (a[i] == b[j]) }); printf("%d", d[i-1][j-1]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ,...
-
[BOJ] 1965 : 상자넣기
1965 : 상자넣기 풀이 lower bound를 써주자! 더 큰 상자가 최소 어디에 들어갈 수 있는지 lower bound로 찾으면 된다! O(n^2) dp대신에 lower bound를 써주면 O(nlogn)에 풀 수 있따! 코드 #include <stdio.h> #include <algorithm> using namespace std; int n, len, a[1001]; int main() { scanf("%d", &n); while (n--) { int tmp; scanf("%d", &tmp); auto it = lower_bound(a, a + len, tmp); if (*it == 0) len++; *it = tmp; } printf("%d", len); return 0; } 아무말...
-
[BOJ] 11055 : 가장 큰 증가 부분 수열
11055 : 가장 큰 증가 부분 수열 풀이 d[i] = i번째 수까지의 부분 수열 중 최댓값으로 놓자! d[i] = d[j] + a[i] lis에서 dp 배열에 길이를 넣는 것 대신 최댓값을 넣어주면 된다. 코드 #include <stdio.h> int n, ans, a[1001], d[1001]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); d[i] = a[i]; for (int j = 0; j <= i; j++) { if (a[j] < a[i] &&...
-
[BOJ] 1699 : 제곱수의 합
1699 : 제곱수의 합 풀이 knapsack 풀듯이 똑같이 풀면 된다! 배낭에 무게가 i*i이고 가치가 1인 돌덩이들을 넣는다고 생각하자! dp[j] = min(dp[j-i*i] + 1, dp[j]) 코드 #include <stdio.h> int n, d[100001]; int min(int a, int b) { return a < b ? a : b; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) d[i] = 1e9; for (int i = 1; i*i <= n; i++) for (int j =...
-
[BOJ] 1309 : 동물원
1309 : 동물원 풀이 d1[i] = 2*i인 우리에서 i번째 칸에 사자를 0마리 놓는 경우의 수 d2[i] = 2*i인 우리에서 i번째 칸의 한 쪽에만 사자를 1마리 놓는 경우의 수 d1[i] = d1[i-1] + d2[i-1] * 2 d2[i] = d1[i-1] + d2[i-1] 위의 식을 그대로 써도 좋지만, 1차원으로 더 압축해보자! 위에서 정의한 d1과 d2를 잘 기억하자. d1[i] = d1[i-1] + d2[i-1] * 2 d1[i] = (d1[i-2] + d2[i-2] * 2) + (d1[i-2] + d2[i-2]) * 2 d1[i]...
-
[BOJ] 2133 : 타일 채우기
2133 : 타일 채우기 풀이 타일은 n이 짝수인 경우에만 완벽히 채울 수 있다. 2*1 타일을 맨위와 맨아래에 일렬로 배치하는 경우에 유의하자. dp[i] = dp[i-2] * 3 + dp[i-j] * 2 (4 <= i, 4 <= j <= i) 코드 #include <stdio.h> int main() { int n, d[31] = { 1,0,3 }; scanf("%d", &n); for (int i = 4; i <= n; i += 2) { d[i] = d[i - 2] * 3; for (int j...
-
[BOJ] 1316 : 그룹 단어 체커
1316 : 그룹 단어 체커 풀이 i번째 문자와 i-1번째 문자가 같다면 둘은 연속된 문자이므로 같은 그룹에 속한다. 단어가 그룹에 속해있지 않는 경우는 이미 앞에서 동일한 문자가 나왔고, i번째 문자와 i-1번째 문자가 다른 경우이다. 체킹 배열을 만들어서 체크해주자! 코드 #include <iostream> #include <string> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int tc, ans = 0; string str; cin >> tc; while (tc--) { bool chk[26] = { 0 }, flg = 0; cin >> str;...
-
제1회 천하제일 코딩대회 본선 문제 풀이
대회 정보와 문제 리스트: https://www.acmicpc.net/contest/view/242 문제 검수에 많은 도움 주신 sgc109, joonas, baactree님 감사드립니다! A. 걷다보니 신천역 삼 (Small) 14650 : 걷다보니 신천역 삼 (Small) 풀이 n 제한이 굉장히 작기 때문에 모든 경우의 수를 전체 탐색 해보면 된다. 코드 #include <stdio.h> #include <math.h> int n, cnt; void gogo(int len, int num) { if (len == n) { if (num % 3 == 0 && num != 0) cnt++; return; } for (int i = 0;...
-
제1회 천하제일 코딩대회 예선 문제 풀이
대회 정보와 문제 리스트: https://www.acmicpc.net/contest/view/241 A. 와이버스 부릉부릉 풀이 14645 : 와이버스 부릉부릉 모두 기분좋게 한 문제씩은 풀고 가라는 의미에서 출제한 문제이다. 시작할 때 한 번 웃고 시작하라고 냈는데 대회장에서 웃는 사람이 아무도 없어서 당황스러웠다 (…) 입력을 받지 않고 문제의 답만 출력해도 되다. 코드 main(){puts("비와이");} B. 욱제는 결정장애야!! 풀이 14646 : 욱제는 결정장애야!! 데스크립션이 어려웠는지 생각보다 정답률이 낮아서 당황스러웠다 (…) 바구니에 똑같은 공이 없으면 공을 바구니에 넣고, 아니면 바구니에 있는 공과 뽑은 공을 버린다. 각...
-
[교육용] STL, 자료구조 및 문제풀이 꿀팁
원래 이번 포스트는 탐색으로 쓰려고 했는데 그래프 그리기 귀찮아서 stl을 쓰기로 했어요 ㅠㅠ stl만 다루는 건 아니고, 문제풀이에 사용되는 몇 가지 스킬들에 대해서도 이야기하려고 해요. 원래 map, set, list 등등 많이 다루려고 했는데 포스트가 교내대회 교육용이기도 하고… 출제범위 밖이기도 하고… 귀찮기도 하고… 그리고 제일 중요한 건! 이 포스트에서는 stl의 사용법에 대해서 다루지 않습니다. 대신 stl을 어떻게 사용해야하는지, stl의 활용법에 대해서 다룹니다. 문법에 대한 건 http://www.cplusplus.com 여기에 다 나와있어요 >_< 그리고 또 어차피 stl 컨테이너가 다...