결국 오고야 마는 것들

처음에 무지성 완탐으로 시도했다가 TLE. 이리저리 식을 써보다가 n, m이 주어졌을 때 만들수 있는 단어가 n+m+1​Cm​개임을 발견해서 풀었다! 좀 더 똑똑했으면 문제 특성을 보고 떠올렸을텐데, 무작정 쓰다가 발견해서 운이 좋았던 것 같기도 하다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; ll cache[205][205];..

혼내주기 2021. 7. 22. 10:47

어이없게 홀짝으로 해당 칸을 몇번 방문했는지 계산하는 것 까지 다 해놓고, N번째를 도착점을 어떻게 계산할지 몰라서 찾아봤다... (x, y)번째 칸은 (x-1, y)칸과 (x, y+1)칸의 방문 횟수의 합인걸 이용해 dp로 n-1번 산책했을 때의 상태를 저장해놓고 n번째는 경로에 맞게 따라가면 된다. dp문제를 별로 안좋아하는데 이번 문제는 뭔가 재미있었다. 나 의외로 dp를 좋아할지도??... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, ..

혼내주기 2021. 7. 22. 10:44

오랜기간 못 푼 상태로 외면하다가 결국 풀었다. 아무리 봐도 우선순위 큐를 쓰지 않고 풀 수 있는데, 계속 틀려서 삽질을 굉장히 오래했다. pq로도 바꿔보고 여러가지 삽질을 하다가 결국 인접행렬이 잘못 된것을 찾아서 인접리스트로 바꾸고 통과했다!@ 뭔가 오래된 때를 벗겨낸 기분이라 기분이 좋다!@ #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1,..

혼내주기 2021. 7. 22. 10:43

이번 카카오 인턴 코테 4번 문제랑 비슷하다고 추천받았던 문제. 풀면서 그때 못푼게 너무 아쉽게 느껴진다. 충분히 풀 수 있었는데... 비트마스크로 어떤 열쇠를 들고있는 상태인지를 포함해서 bfs를 돌리면 된다. 비트마스크가 뭔지 모른다면 이 글을 참고해보자!! #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; struct state {..

혼내주기 2021. 7. 22. 10:42

끔찍한 구현 문제. 최대 깊이가 10이기 때문에 총 경우의 수가 410으로 완전탐색으로 풀 수 있다. 물론 캐쉬를 적용하면 훨씬 빨리 답을 구해낸다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; struct state { pii R, B; int d; state(pii r, pii b, int dd) {R = r, B = b, d ..

혼내주기 2021. 7. 21. 12:22

심금을 울리는 제목... 경로에서 남-남 혹은 여-여 경로를 제외하고 크루스칼을 돌리고 연결된 노드의 수가 n과 같은지 확인하면 된다. 처음으로 유니온 파인드에서 갯수가 중요한 문제를 풀었는데 꽤 재미있다. 어렵게 내면 매우 어려울 수 있을듯. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; vector adj; int parent[1..

혼내주기 2021. 7. 21. 12:20

sds 알고리즘 특강을 들으면서 풀었다. 여기서 만든 parent 배열을 채우는 기법을 sparse table이라고 하는 것 같던데, 어떻게 이런 생각을 해냈는지 놀라울 뿐이다... log(n)으로 n번째 부모를 빠르게 찾는게 핵심인 것 같다. 세그먼트 트리도 그렇고 컴퓨터에서 2의 힘이란 정말... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -..

혼내주기 2021. 7. 21. 12:18

lca 응용 문제. sparse table로 2의 지수승의 부모 노드를 저장했듯 최솟값과 최댓값 배열을 만들어서 저장하면 된다. 이 문제를 풀면서 lca와 sparse table을 좀 더 이해한 것 같아서 기분이 좋다!@ #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; const int N = 17; vector adj[100001];..

혼내주기 2021. 7. 21. 12:17