-
[BOJ] 13302 : 리조트
13302 : 리조트 풀이 다이나믹 프로그래밍! dp[i][j] = i번째 날에 쿠폰 개수가 j인 경우의 수! 룰루랄라 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 100 + 10; const int price[] = { 0,10000,25000,37000 }; const int INF = 987654321; int n, m; int dp[n_][n_ * 2]; bool chk[n_]; void upd(int i, int j, int v) { if (dp[i][j] > v || dp[i][j] == INF) dp[i][j] = v; } int main() { scanf("%d %d",...
-
[BOJ] 1786 : 찾기
1786 : 찾기 풀이 KMP 룰루랄라 코드 #include <stdio.h> #include <vector> #include <string.h> using namespace std; const int N_ = 1e6 + 5; int fail[N_], t_len, p_len; char T[N_], P[N_]; int main() { gets_s(T); t_len = strlen(T); gets_s(P); p_len = strlen(P); for (int i = 1, j = 0; i < p_len; ++i) { while (j && P[i] != P[j]) j = fail[j - 1]; if (P[i] == P[j]) fail[i] = ++j; } vector<int> ans;...
-
[BOJ] 1701 : Cubeditor
1701 : Cubeditor 풀이 Naive한 풀이 룰루랄라 코드 #include <bits/stdc++.h> using namespace std; int ans, cnt; char str[5001]; vector<string> suf; int main() { scanf("%s", str); for (int i = 0; i < strlen(str); ++i) { suf.push_back(str + i); } sort(suf.begin(), suf.end()); for (int i = 0; i < suf.size() - 1; ++i) { while (suf[i][cnt] == suf[i + 1][cnt]) ++cnt; ans = max(ans, cnt); cnt = 0; } printf("%d", ans); return 0; } 아무말 백준,...
-
[BOJ] 7976 : 수열
7976 : 수열 풀이 좋은 풀이는 여기에 있다! 핵심은 이거: dp[i][j] = i번까지의합 % 2가 j인 최소 변환 횟수 코드 #include <stdio.h> #include <algorithm> using namespace std; int N, K; int cnt[1000001][2], dp[1000001][2]; int main() { scanf("%d %d", &N, &K); for (int i = 0; i < N; ++i) { int a; scanf("%d", &a); ++cnt[i % K + 1][a & 1]; } dp[0][1] = 1e9; for (int i = 1; i <= K; ++i) {...
-
[BOJ] 1019 : 책 페이지
1019 : 책 페이지 풀이 나중에 써야지~ 코드 #include <stdio.h> int N, prev; int cnt[10]; int main() { scanf("%d", &N); for (int i = 1; N; i *= 10) { int now = N % 10; N /= 10; for (int j = 0; j < now; ++j) cnt[j] += (N + 1) * i; cnt[now] += N * i + prev + 1; for (int j = now + 1; j < 10; ++j)...
-
[BOJ] 12101 : 1, 2, 3 더하기 2
12101 : 1, 2, 3 더하기 2 풀이 지금 생각해보니 스택으로 짜도 될 것 같다. 코드 #include <stdio.h> #include <vector> using namespace std; int N, K; int res; vector<int> ans; bool go(int sum, int cnt) { if (sum == N) ++res; if (res == K) return true; for (int i = 1; i <= 3; ++i) { if (sum + i <= N) { if (go(sum + i, cnt + 1)) { ans.push_back(i); return true;...
-
[BOJ] 14442 : 벽 부수고 이동하기 2
14442 : 벽 부수고 이동하기 2 풀이 dp[x][y][부순 벽의 수 k]로 두고 풀자. BFS를 돌리면 된다. 하지만 중요한 건 문제 풀이가 아니고(!) memset이 byte 단위로 초기화하기 때문에 memset(dp, 1, sizeof(dp)) 하면 dp의 각 방이 0x01010101 이렇게 채워진다는 걸 배웠다. 그래서 987654321이나 1e9처럼 int_max 절반으로 초기화하고 싶으면 0x3f로 초기화하면 된다. 음… 어셈 공부하다 말았는데 계속 해야하나? ㅠㅠ 코드 #include <stdio.h> #include <queue> #include <algorithm> using namespace std; const int dx[] = { 0,1,-1,0 }; const int...
-
[잡담] 좋은 대학이 가지는 장점은 뭐가 있을까요?
좋은 대학이 가지는 장점? #97 위 링크는 학교 질의응답 커뮤니티(아직 베타 서비스라 깃허브 이슈로 관리 중)에 올라온 질문이다. 자주 올라올 것 같은 질문이라 내 생각을 한 번 정리해서 답변해봤다. 물론 지극히 개인적인 답변 시점에서 내가 가진 생각일 뿐, 사람마다 생각이 다를 수 있고, 내 생각이 당장 5분 뒤에 변할 수도 있다. 아래는 내 답변. 좋은 대학의 기준은 사람마다 달라요. 각자 사람마다 추구하는 가치가 다르고 학교마다 추구하는 인재상이 다르기 때문이에요. 말씀하신 좋은 학교는 통상적으로 이야기하는 sky를...
-
[BOJ] 2532 : 먹이사슬
2532 : 먹이사슬 풀이 문제를 풀고 나서 다른 분들의 코드를 보다가 lower_bound를 저렇게 쓸 수 있다는 사실에 감명받았다. 양수가 음수로 변하면, 양수일 때 더 큰 수가 음수에선 더 작은 수가 되는데 양수 중에서 작은 수와 음수 중에서 가장 작은 수를 고르게 되면 넓은 범위를 찾게 된다. *lower_bound(res, res + i, now) = now;를 통해 먹이사슬인지 판단할 수 있다. 새로운 데이터가 쌓이지 못하고 덮어쓰게 되면 INF의 값이 배열의 뒤쪽에 누적되게 되고, INF의 lower_bound가 답이 된다. 코드...
-
[BOJ] 1300 : K번째 수
1300 : K번째 수 풀이 임의의 숫자 m을 골라서 K번째 숫자인지 판단해보자! 그 임의의 숫자 m은 무려 O(log K)에! 무려 이분 탐색으로 찾아보자! 그렇다면 떠오르는 질문, m 보다 작은 숫자의 개수를 어떻게 하면 빠르게 구할 수 있을까? A[i][j]에서, i행에 속한 숫자들은 i*j이므로 모두 i의 배수이다. 그러므로 min(mid/i, N)이 i번째 행에서 mid보다 작은(= 임의의 m보다 작은) 숫자들의 개수가 된다. eg. N = 1000인 경우, 첫 mid가 1000*1000/2 = 50만이 되는데, 50만/i가 N을 넘어갈 수 있으므로 min(mid/i,...