BOJ
-
[2109] 순회강연BOJ 2022. 2. 12. 21:58
https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net i일에 진행되는 강연을 갈지를 판별해야 한다고 보면, [1, i]일에 진행되는 모든 강연을 큐에 넣는다. 큐의 size()가 i보다 크다면, size를 i로 맞추기 위해서 가장 싼 강연부터 빼준다. 로직은 매우 간단하고 직관적인데 구현방식에 대한 고민이 필요하다. 2중 loop로 구현하면 간단하겠지만, 그 경우 강연 선택 여부에대한 bool []이 추가적으로 필..
-
[1941] 소문난 칠공주BOJ 2022. 2. 12. 15:30
https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 백트래킹으로 풀면 3방향 이상의 교차로를 재방문해줄 일이 있어서 방문처리가 까다롭다. 25C7개의 경우의 수를 만들고, 해당 경우의 수가 정답의 가능성이 존재하는지를 판정하는 문제로 바꿔 푸는게 편하다. #include using namespace std; using pi = pair; constexpr int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0}; char..
-
[13023] ABCDEBOJ 2022. 2. 11. 04:02
https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 백트래킹 하듯 탐색하다, depth가 4가 되었을때 1을 출력한다. #include using namespace std; int n, m; vector adj[2001]; bool vst[2001]; void f(int x, int cnt) { vst[x] = true; if (cnt == 4) { cout n >> m; int i; for (i = 0; i > A >> B; adj[A].push_back(B); adj[B].push_back(A); } for (i = 0; i
-
[16929] Two DotsBOJ 2022. 2. 11. 04:00
https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net dfs로 탐색하다, depth가 4이상일때 시작한 위치를 만났으면 Yes. 모든 시작점에 대해 dfs를 호출해주면 된다. #include using namespace std; const int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0}; int n, m, ey, ex; char a[55][55]; bool vst[55][55]; void f(int c..
-
[5397] 키로거BOJ 2022. 2. 11. 03:59
https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net list를 사용해서 구현해주면 된다. erase는 it의 한칸 왼쪽을 지우고, erase()가 반환하는걸 그대로 넣어준다. #include using namespace std; int t; list l; string s; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> t; while (t--) { l.clear(); a..
-
[11758] CCWBOJ 2022. 2. 11. 03:57
https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net ccw 기본문제 #include using namespace std; typedef struct { int x, y; } point; int ccw(point a, point b, point c) { return (a.x * b.y + b.x * c.y + c.x * a.y) - (b.x * a.y + c.x * b.y + a.x..
-
[1035] 조각 움직이기BOJ 2022. 2. 10. 03:06
https://www.acmicpc.net/problem/1035 1035번: 조각 움직이기 최대 5개의 조각이 있는 5×5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net 입력된 조각의 개수를 S라고 하면, 25^S로 완전탐색하면 된다. 각 조각이 어느위치로 움직일지가 결정되면, 모든 S개의 조각에 대해서 맨해튼 거리를 합한것이 score가 된다. 해당 score를, 모든 조각이 붙어있는 경우에 한해서 ans를 최소로 업데이트하면 된다. 조각이 붙어있는지를 판정하는건 실버정도의 문제, dfs든 bfs든 간단히 판정할 수 있다. 여러모로, 구현난이도가 높은데.. ..
-
[1167] 트리의 지름BOJ 2022. 2. 10. 01:08
https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 아무 노드를 하나 잡고 거리가 가장 먼 노드가 트리의 지름을 이루는 첫 번째 노드이고, 그 노드에서 가장 먼 노드가 트리의 지름을 이루는 두 번째 노드다. 증명도 직관적이고, typical한 유형인 것 같지만, dfs와 트리의 정의만 아는 상태에서 떠올리기엔 만만찮다. #include using namespace std; using pi = pair; vector adj[10000..
-
[1240] 노드사이의 거리BOJ 2022. 2. 9. 01:06
https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 임의의 두 노드에 대해서, 트리라는 특성으로 인해 경로는 항상 유일함이 보장된다. 그렇기에 최단경로 알고리즘을 사용할 필요 없이, bfs든 dfs든 그래프를 만들어서, 탐색할 뿐인 문제가 된다. #include using namespace std; using pi = pair; int n, m; vector adj[1001]; typedef struct { int idx, cost; } state; int f(int s, int tar) { ..
-
[1865] 웜홀BOJ 2022. 2. 8. 16:08
https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 여러모로 세심히 신경써줘야 하는 부분이 많다. "[1219] 오민식의 고민"과 달리, 음수 사이클에서 시작으로 돌아올 수 있는지를 판정할 필요는 없다. 시작 정점을 선정하는데에 완전히 자유로우므로, 음수 사이클을 이루는 노드가 곧 시작이라고 생각해도 된다. 거리와 관계없이, 음수 사이클의 여부만 파악하면 되므로, 모든 정점을 대상으로 갱신을 진행한다. #include using nam..