Little Jay

Priority Queue를 활용하는 Greedy Technique를 활용하는 문제였다. 난이도가 왜 Silver 1인지 이해를 못하겠지만 간단한 풀이는 pq를 min이 top에 오게 만든 다음 앞의 두 개를 더한 값을 두번 push해주면 된다. 그리고 크기가 매우 클 가능성이 있기 때문에 long long 자료형을 사용해야 AC를 받을 수 있다. #include #define endl '\n' #define ll long long using namespace std; priority_queue pq; int n, m; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i < n;..

간단한 다익스트라를 활용한 웰노운 문제 크게 어려운 문제는 아니었지만 다익스트라가 무향그래프일때 동시에 그래프를 업데이트 하는 것을 잊지 말자. #include #define endl '\n' #define INF 987654321 #define pii pair using namespace std; int n, m; vector v[50001]; int dist[50001]; priority_queue pq; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i > a >> b >> w; v[a].push_back({ w, b ..

실제 뿌요뿌요 게임을 구현하는 문제였다. 아이디어는 이렇다 4개 이상의 같은 색깔의 슬라임(?)이 모이면 터지고 1연쇄가 일어난 후 뿌요들이 아래로 중력에 의해 내려온다. 이 문제를 풀때 간과했던 것은 한 번에 터뜨릴 수 있는 것들은 한번에 터지고 이는 1 연쇄이다. 그래서 한번에 2개의 그룹이 터져도 2연쇄가 아니라 1연쇄이다. 이 부분을 제외하면 재밌게 풀었던 문제이다. #include #include #define endl '\n' using namespace std; char graph[12][6]; bool visited[12][6]; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }; int ans = 0; //일반 bfs ..

빡구현 문제이다. 여기서 어려웠던 부분은 명령어 별로 벽에 부딪혔을 때 나머지 명령어도 받아야 하는 부분의 처리가 좀 까다로웠다. 구조체를 활용하여 위 부분만 조심하면 크게 어렵지는 않았던 문제였던 것 같다. #include #define endl '\n' using namespace std; int a, b; int n, m; int num, orders; char action; struct rb { int x; int y; char direction; }; rb robots[101]; bool checkWall(int num) { if (robots[num].x b) { cout > y >> dir; robots[i].x = x; robots[i].y = y; robots[i].direction = ..

쉬웠던 구현문제였지만 오타 하나를 못봐서 30분간 맞왜틀하고 있었던 문제였다. 처음에는 이차원 배열을 통해서 구현해야하나 싶었는데, 생각해보면 deque를 사용하면 좋겠다라는 생각을 했다. 컨베이어벨트를 회전시킬 때 단순히 push_front, pop_back을 해주면 컨테이너가 잘 회전이 된다. 생각없이 check 컨테이너에 push_back 써놓은거를 못봐서 애먹었다. 벨트 회전 - 로봇 움직이기 - 로봇 배치 - 내구도 체크 순서대로 진행하면 된다. 특히 로봇은 0~n-1에서 놀고 n ~ 2n -1에 절대로 가지 않는다. 어차피 n-1에서 다 떨어져야하기 때문이다. #include #define endl '\n' using namespace std; int n, k; deque durability;..

순간 다익스트라 어떻게 작성했지? 하고 헷갈렸던 문제이다. 다익스트라 알고리즘은 우선순위 큐를 사용해야 하기 때문에 이 컨테이너를 사용할 때 greater을 사용하길 원한다면 weight, vertex 순으로 pair을 만들어서 넣어야한다. 이 문제는 다익스트라를 3번 수행함으로서 해결할 수 있다. 1번에서 시작하는 경우, u에서 시작하는 경우, v에서 시작하는 경우에 대해서 다익스트라를 각각 돌리고, 1번에서는 u, v까지의 최소 거리, u에서는 v와 n까지의 거리, v에서는 n까지의 거리를 구한 후 1-u-v-n, 1-v-u-n의 Case에 대해서 min값을 구해주면 된다. 예상하지 못했던것은 Overflow의 존재이다. INF값을 먼저 체크하지 않고 min값을 구한 후 체크를 하기 때문에 Overf..

다익스트라를 활용한 간단한 문제. 다익스트라를 사용하면서 거리가 k가 될때 정답 벡터에 넣어주면 된다. #include #define endl '\n' #define INF 987654321 #define pii pair using namespace std; int n, m, k, x; vector v[300001]; int dist[300001]; vector ans; void dijikstra(int start) { for (int i = 0; i current_dist + next_dist) { dist[next] = current_dist + next_dist; pq.push({ dist[next], next }); if (dist[next] == k) ans.push_back(next); } }..

Disjoint - Set 문제. 이를 분리 집합이라고도 하는데 Disjoint-Set이 더 어울리는 것 같다. 이 문제는 O(n)에 풀면 안되는 문제이다. Disjoint-Set의 find는 항상 최고의 조상을 찾아야하기 때문에 시간을 줄이는 곳에서 애를 먹었다. 이 방식을 Path Compression 방법으로 사용하면 AC를 받을 수 있다. #include #define endl '\n' using namespace std; int n, m; int p[1000005]; int op, a, b; int find(int x) { if (x == p[x]) return x; else return p[x] = find(p[x]); } void unite(int x, int y) { x = find(x);..

간단했던 BFS 문제였는데 멍청하게 BFS 수행 조건을 잘못 줘서 30분동안 맞왜틀 하고 있던 문제였다. 특별한 로직은 따로 없었고 양의 수 > 늑대 수 일때만 양의 수를 업데이트 시키는 것만 잘 파악했다면 크게 거렵지는 않았다. #include #define endl '\n' using namespace std; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }; char board[255][255]; bool visited[255][255]; int r, c; int wolves = 0, sheep = 0; void bfs(int x, int y) { queue q; q.push({ x, y }); visited[x][y] = tr..

좀 비효율적인 코드이긴한데 전체적인 로직에서 크게 다를점이 없다. 결과적으로 '-'가 언제 들어오는지가 관건이 된다. https://www.acmicpc.net/board/view/86898 여기에 반례가 정리되어 있는데 이 반례를 보면 결국 '-'가 한번 들어오고 '+'가 들어와도 괄호를 끝까지 쳐버리면 되고, '-'가 연속적으로 들어오게 된다면 그냥 괄호를 치지 않고 계속해서 빼기만 해주면 된다. 이 점만 좀 유의하면 한 번에 correct이 뜰 수 있었을텐데 아쉽다. 코드는 좀 지저분하고 비효율적이라 로직만 참고하시길 바란다. #include #define endl '\n' using namespace std; string s, num; int temp; int main() { ios::sync_w..