BLUE DOLPHIN

https://www.acmicpc.net/problem/10545 만약에 map이 없었다면... 이걸 어떻게 풀었을까 STL을 만들어 주신 모든 분에게 감사드립니다. #include using namespace std; const char alphabet[10][5] = { {}, {}, {"abc"}, {"def"}, {"ghi"}, {"jkl"}, {"mno"}, {"pqrs"}, {"tuv"}, {"wxyz"} }; int main() { ios_base::sync_with_stdio(false), cin.tie(0); string str; map m; for (int i = 1, a; i > a; for (int j = 0; alphabet[a][j]; ++j) m[al..

https://www.acmicpc.net/problem/2698 D[n][k][lb]: 길이가 n이고 연속된 비트가 k개이면서 마지막 비트가 lb(0 또는 1)인 수열의 개수 처음에는 D[n][k]으로만 점화식을 세워보려고 했는데 끄적끄적하다 보니 결국에는 마지막 비트와 관계가 있어서 어쩔 수 없이 사용하게 되었다. 마지막 비트가 0일 때 D[n][k][lb] = D[n - 1][k][0] + D[n - 1][k][1] 마지막 비트가 0인데 길이는 n이고 연속된 비트가 k인 수열의 개수는 길이 n-1짜리에서 마지막 비트가 0, 1인 두 개의 수를 합치면 된다. ex) 11100, 01110 -> 1110에서 0하나 붙이면 되고, 0111에서 0하나 붙이면 된다. 마지막 비트가 1일 때 D[n][k][l..

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 ==..