결국 오고야 마는 것들

brute force 문제. 처음에 방문 체크를 위해 int cache[1000005][11]; 이런 배열을 선언하고 stoi로 확인했는데, 고수들의 풀이를 보니 set이나 map을 사용했길래 또 한 수 배웠다. 특히 이 문제 같은 경우는 나올 수 있는 경우의 수가 6!밖에 안되기 때문에 메모리를 왕창 아낄 수 있다. 오늘의 교훈: dp는 map hashmap으로도 할 수 있다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; set cache[11]; int n, m, k, ans = 0; bool able = false; void input() { fastio; cin >> n >> k; } void d(..

혼내주기 2021. 7. 22. 11:00

#include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; const int n = 10; bool cache[1 c; if(c == 'O') arr[i][j] = true; else arr[i][j] = false; } } } void click(vector& m, int x, int y) { m[x][y] = !m[x][y]; for(int i = 0; i = n || ny = n) co..

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

상태를 야무지게 사용하는 bfs. x좌표, y좌표, 이동한 거리, 부순 횟수, 밤낮 총 5가지 상태를 큐에 넣고 bfs를 돌리면 된다. dx dy에 움직이지 않는 경우도 넣었더니 벽이 연속으로 나오는 경우를 처리하지 못해서 조금 헤맸다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; bool visited[1000][1000][11][2], arr[1000][1000]; int n, m, K; struct state { int x, y, d,..

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

머지소트트리로 풀었는데, 좌표를 압축해서 그냥 세그로 풀면 메모리를 훨씬 줄일 수 있어서 다시 풀었다. 능력의 범위는 10억까지지만 총 갯수는 500000이므로 좌표 압축을 하고 각각이 leaf인 세그를 만든다. 이후 들어온 사람 순서대로 [0,자신의능력) 구간에 몇명이나 있는지 쿼리를 날리고 매번 해당 사람을 update 해주면 된다. #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[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1};..

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

#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[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; pii p; int dist[1005][1005]; bool arr[1005][1005]; int n, m, L, R; struct state { int x, y, d, l, r; state(int xx, int yy, int dd, int ll, int rr) { x = xx, y = yy, d = dd, l = ll, r = rr; ..

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

knapsack의 냄새가 나지만 속지않고 그리디로 담을 수 있는 무게가 가장 작은 가방부터 담을 수 있는 최고 가격의 보석을 담으면 된다는 것, 우큐를 사용하면 되겠다 까지 떠올렸는데, 어떻게 구현할지 떠올리지 못했다... 가장 작은 가방부터 담을 수 있는 모든 보석을 우큐에 넣고, 하나씩 꺼내면 된다. 정렬 문제가 은근 약한 것 같다. 예전에 백준의 Q-인덱스 문제도 못풀고, 프로그래머스에서 똑같은 문제를 또 못푼게 기억이 난다... 아무래도 정렬 문제를 복습해야 겠다... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define ..

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

#include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; using pll = 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 = 1 years[i] >> tree[i+N]; for(int i = N-1; i; --i) tree[i] = max(tree[i Y >> X; int ret = solve(Y, X); if(ret == 0) cout

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

1 ~ 10까지의 수를 소인수분해하면 다음과 같다. 오민식을 만족하는 수는 오른쪽처럼 1부터 N까지의 수를 소인수분해하는 과정에서 각 소수의 최대 갯수이다. 에라토스테네스처럼 소수를 찾을 때 마다 소수가 최대 몇개 필요한지 찾아서 곱하면 된다. (스포주의) 중간에 0이 나와서 계속 찍어봤는데, 987654321로 나누어지는 수가 있었다...(!!) N이 1000000도 답이 0이어서 맞게 풀었나 몇번이나 찍어봤다. #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]..

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