-
[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 컨테이너가 다...
-
[교육용] 이분 탐색
안녕하세요! 이번 포스트에서는 binary search에 대해 이야기 해보겠습니다. binary search, 이분 탐색은 어떤 정렬된 범위 내에서 우리가 원하는 값을 빠르게 찾기 위한 탐색 방식입니다. 예시 문제 https://www.acmicpc.net/problem/1920 수 찾기 n개의 정수열 중에 어떤 숫자 X가 존재하는지 판단하는 문제입니다. 평범하게 구현했을 때, X가 존재하지 않는 최악의 경우 n개의 모든 숫자를 돌아보아야 하므로 시작복잡도는 O(n)이 됩니다. 하지만 이분 탐색을 이용하면 O(n)을 O(log n)으로 줄일 수 있습니다. 이게 얼마나 빨라진 거냐면, 2^100번 돌아야하는 작업을 100번만 돌아서 끝낼 수...