BLUE DOLPHIN

https://www.acmicpc.net/problem/11779 다익스트라를 구현하는데 경로를 저장해야 한다. 추적방법 trace 배열을 선언한다. 다익스트라 알고리즘에서 거리 업데이트하는 부분에 trace[nxt.idx] = now.idx로 지정한다. 도착 지점부터 trace 배열을 돌면서 t = trace[t]를 통해 노드 A로 오기 전 노드로 t를 변경한다. #include using namespace std; struct Edg { int idx, fair; Edg(int i, int f) : idx(i), fair(f) {} bool operator nxt.fair + now.fair) { dist[nxt.idx] = nxt.fair + now.fair; trace[nxt.idx] = now..

https://www.acmicpc.net/problem/14442 전형적인 BFS에 벽 부술 수 있는 조건을 붙인 문제이다. 보통 이런 문제들은 visit 배열을 visit[x][y][cnt]로 정의해서 구할 수 있다. 이런 건 코드를 보면서 할 게 나을 것 같다. if (Map[nxtX][nxtY] == '0' && vst[nxtX][nxtY][now.cnt] == INF) { vst[nxtX][nxtY][now.cnt] = vst[now.x][now.y][now.cnt] + 1; Q.push({ nxtX, nxtY, now.cnt }); } else if (now.cnt + 1 nxtX || nxtX >= N || 0 > nxtY || nxtY >= M) continue; if (Map[nxtX][..

https://www.acmicpc.net/problem/1727 남자를 기준으로 잡고 풀었다. D[i][j]: i번째 남자까지와 j번째 여자까지 짝을 맺었을 때 성격 차이의 최소합 D[i][j] = D[i - 1][j - 1] + abs(man[i] - girl[i]) if(i > j) D[i][j] = D[i - 1][j] - 남자가 여자보다 많아서 짝을 지을 수 없음 if(i 사실 이렇게 생각하는게 맞는지 모르겠다. 어쨋거나 핵심인 짝을 만들거나, 만들지 않거나를 점화식으로 세운 것이다. 저 세 식 중 최소인 값을 D[i][j]의 값으로 업데이트한다. 또한 남녀 입력 받은 수열을 정렬해줘야 하는데 그..

https://www.acmicpc.net/problem/2775 D[i][j]: i층 j호의 거주민 수 D[0][i] = i D[i][j] = D[i - 1][for k: 1...j] #include int D[15][15]; int main() { int T; for (int i = 1; i

https://www.acmicpc.net/problem/10250 풀이가 2가지 방법이 있다. 하나는 직접 for문을 통해 계산하는 방법. 다른 하나는 규칙을 통해 계산하는 방법. 근데 보통 다른 상황과 엮이지 않고 이 상태에서의 답을 구하는 문제들은 규칙성을 노리고 내는 문제들 같다(개인적인 생각) 규칙 층: (N - 1) % H + 1 호: (N - 1) / H + 1 -1 후에 +1을 해주는 이유는 N과 H가 같은 경우에 발생하는 문제가 있다. H(전체 층수)가 3일 때 N = 3인 경우 N % H로 계산하면 0층이 된다. 그래서 그렇다. 호도 저렇게 해주는 이유가 위와 비슷하다 N == H일 때 N / H + 1이면 1이어야 하는데 2가 된다. #include int main() { int T;..

https://www.acmicpc.net/problem/1967 트리의 지름이란 트리에서 노드 간 가장 긴 길이를 의미한다. DFS를 아무 점에서 시작해서 가장 긴 부분의 위치를 찾는다. 그리고 그 위치에서 DFS를 돌려 가장 긴 부분을 찾는다. 그래서 나온 길이가 트리의 지름이 된다. #include #include #include using namespace std; typedef pair pii; int n, res, idx; vector v[10001]; bool visited[10001]; void DFS(int d, int h) { visited[h] = true; if (d > res) res = d, idx = h; for (auto &i : v[h]) { if (!visited[i.fi..

https://www.acmicpc.net/problem/6603 재귀함수로 구현할 수 있는데, 현재 인덱스를 선택하거나 안 하거나 둘 다 재귀함수로 호출을 해서 모든 경우를 출력할 수 있게 된다. 매개변수는 인덱스와 카운트로 설정해줘서 카운트가 6이되면 추가한 숫자들을 출력하도록 하면 된다. 출력용 배열은 vector를 사용할 수도 있지만 일반 배열을 사용하려면 P[cnt + 1](출력용) = S[idx + 1](기존 배열)로 변경해주면 된다. #include using namespace std; int s[50], b[7], N; void printAll(int idx, int cnt) { if (cnt == 6) { for (int i = 1; i = N) return; b[cnt + 1] = s[..

https://www.acmicpc.net/problem/2178 4방향으로 BFS를 돌면 된다. #include #include using namespace std; const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}; int n, m; char a[102][102]; int vst[102][102]; struct ED { int x, y; ED(int x, int y) : x(x), y(y) {} }; int BFS(int x, int y) { queue q; q.push(ED(x, y)); vst[x][y] = 1; while (!q.empty()) { int xx = q.front().x, yy = q.front().y; q.pop(); if (xx ==..

https://www.acmicpc.net/problem/11383 제목만 읽었을 땐 되게 간단한 문제일줄 알았지만 생각보단 머리를 써야 하는 문제였다. 첫 줄의 문자열을 A, 둘째 줄의 문자열을 B라고 하면 A[i] == A[i / 2](i: 1...2*N)인지 확인한다. #include using namespace std; int main() { ios_base::sync_with_stdio(false), cin.tie(0); int N, M; cin >> N >> M; array s, c; for (int i = 0; i > s[i]; for (int i = 0; i > c[i]; for (int j = 0; j < 2 * M; ++j) if..

https://www.acmicpc.net/problem/4999 문제 설명을 제대로 이해하지 못해서 재환이가 말하는 소리는 항상 "aaah"인 줄 알았다. 하지만 아니었다는 점. a의 개수를 세서 재환이가 부족하게 질렀다면 병원에 가게 하면 된다. #include #include using namespace std; int main() { cin.tie(0), ios_base::sync_with_stdio(false); string s1, s2; int cnt = 0, cnt2 = 0; cin >> s2 >> s1; for (auto &i : s2) if (i == 'a') cnt2++; for (auto &i : s1) if (i == 'a') ++cnt; if (cnt