Haruponea

https://www.acmicpc.net/problem/1854문제에서 최단거리 + 시작 위치 고정 + 양수 비용이라는 점에서 다익스트라를 사용할 수 있다는 점을 알 수 있었다. 하지만 다익스트라는 "최단"거리를 구할 때 사용하기 때문에 약간의 변형이 필요한 문제였다.K번째 최단 경로를 구하기 위해서는 1번째 최단경로의 cost, 2번째 최단 경로의 cost...K-1번째 최단 경로의 cost를 알고 있어야한다. 하지만 K+1번째 cost부터는 필요가 없다. 또한 시작점에서 A라는 노드로 이동하는데 걸리는 newCost과 이미 알고있는 A까지 이동하는데 필요한 cost1, cost2,... ,costK가 있다고 하자. 이때 newCost과 유의미한 비교가 되는 것은 이미 알고 있는 값들(cost 1, ..

https://www.acmicpc.net/problem/11438Lowest common ancestor 유형의 전형적인 문제이다. 가장 먼저 떠오르는 아이디어는 아마 두 노드의 높이를 같게하고 하나씩 올라가면서 같아지는 경우 노드를 출력하는 것일텐데 이렇게 구현하면 시간초과가 난다. 그래서 sparse table이라는 테크닉을 사용해야한다. 처음 풀이에서 하나씩 올라가면서 찾는 것이 아닌 2^K만큼씩 이동하면서 찾는 것이다.일단 모든 숫자는 이진수로 나타낼 수 있고 이를 2^K만큼씩 이동하면서 표현할 수 있다. 예를 들어 7은 0b1011이 될것이고 이는 2^2+2^1+2^0이 될것이다. 이것에 아이디어를 얻어 다음과 같은 p[k][i]라는 table을 만든다. 이 table의 의미는 i번 노드의 2..

https://www.acmicpc.net/problem/2243처음 보고 힙이나 정렬을 사용해야할 것같았지만 원소의 빈번한 추가/제거/업데이트 가 있어서 매번 적절한 위치를 찾고 다시 정렬하는게 쉽지 않아 보였다. 그래서 indexed tree를 사용했다.leaf에는 맛이 i인 사탕의 수를 저장하였다. 그 후 부모노드는 자식 노드의 합으로 저장하였다. 이렇게 하면 리프노드부터 시작하여 자식 노드를 보면서 n번째 사탕이 왼쪽 자식에 있는지 오른쪽 자식에 있는지 알 수 있고 최종적으로 적절한 위치에 있는 사탕을 꺼내 줄 수 있게 된다.#include #include #include #include #include #include #include #include #include using namespace ..

https://www.acmicpc.net/problem/7569 #include using namespace std; #define X first #define Y second int board[102][102][102]; int vis[102][102][102]; int dx[6] = {1, 0, -1, 0, 0, 0}; int dy[6] = {0, 1, 0, -1, 0, 0}; int dz[6] = {0, 0, 0, 0, 1, -1}; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int ans = 1; int m, n, h, z, x, y; cin >> m >> n >> h; queue q; for (int i = 0; i < h; i++) for..

https://www.acmicpc.net/problem/10026 #include using namespace std; #define X first #define Y second string board[102]; int vis[102][102]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int RGBBFS(int n) { //적록색약인 경우 int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (vis[i][j] == 0) { ans++; queue q; q.push({i, j}); vis[i][j] = 1; char curColor = board[i][j]; whi..

https://www.acmicpc.net/problem/1012 #include using namespace std; #define X first #define Y second int board[52][52]; int vis[52][52]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n, m, k, x, y, ans = 0; cin >> m >> n >> k; for (int i = 0; i < 52; i++) { fill(board[i], board[i] + 52, 0); fill(vis[i..

https://www.acmicpc.net/problem/1697 #include using namespace std; int dist[100002]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); fill(dist, dist + 100002, -1); int n, m; cin >> n >> m; if (n == m) cout 100000) continue; if (dist[next[i]] != -1) continue; if (next[i] == m) { cout

https://www.acmicpc.net/problem/4179 #include using namespace std; #define X first #define Y second string board[1002]; int vis[2][1002][1002]; // vis[0]는 불, vis[1]은 지훈 int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; queue q1; // 불 queue q2; // 지훈 for (int i = 0; i > board[i]; for (int j = 0; j ..

https://www.acmicpc.net/problem/7576 #include using namespace std; #define X first #define Y second int board[1002][1002]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n, m, ans = 1; bool is_every = true; cin >> m >> n; queue q; for (int i = 0; i > board[i][j]; if (board[i][j] == 1) ..

https://www.acmicpc.net/problem/2178 #include using namespace std; #define X first #define Y second char board[102][102]; int dist[102][102]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for (int i = 0; i > s; for (int j = 0; j < m; j++) { board[i][j] = s[j]; } } for (int i = 0; i <..