-
[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,...