전체 글
-
[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..
-
[1039] 교환BOJ 2022. 2. 7. 23:02
https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 연산 도중에라도 맨 앞에 0으로 시작하는 정수가 만들어지면 안된다. 정답 업데이트는 정확히 연산을 'K번' 수행했을때에만 업데이트 해주며, string간의 사전순 비교로도 가능하지만, 1'000'000이하의 범위이니 int로 비교해주었다. 상태를 (숫자, 연산횟수)로 놓고, M^2으로 string을 swap해서 나온 결과를 모두 찾는다. 만들 수 있는 상태가 굉장히 희소하기 때문에, set으로 방문처리를 하는것도 나쁘지 않은 방법으로 보인다. #include usin..
-
[1175] 배달BOJ 2022. 2. 7. 15:46
https://www.acmicpc.net/problem/1175 1175번: 배달 어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사 www.acmicpc.net "[16933] 벽 부수고 이동하기 3"과 "[1194] 달이 차오른다, 가자."를 묘하게 섞었다. 하나의 상태를 잘 정의해주어야 하는데, (y, x)는 자명하니, 상태를 구성하는 다른 요소를 살펴보자. 벽 부수고 이동하기 3 처럼 이전방향의 이동에 대한 정보를 저장해야 한다. 벽 부수고 이동하기는 현재의 turn이 짝수이냐와 홀수이냐를 이용해 상태가 달라졌다면, 이 문제는 이전에 어느 방향에서 왔는지로 상태..
-
[11657] 타임머신BOJ 2022. 2. 6. 21:28
https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만포드 기본 문제 #include using namespace std; using ll = long long; using pi = pair; const ll INF = (ll)1e13; ll n, m, dst[505]; vector adj[505]; bool minusCycle = false; int main(void) { ios_ba..
-
[1219] 오민식의 고민BOJ 2022. 2. 6. 21:21
https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 간선의 가중치의 의미를 잘 생각해보면, 교통수단의 가격이 해당 도시에서 벌 수 있는 돈보다 더 적은 경우에는 음수간선이 만들어지게 되므로 벨만포드를 사용해야만 한다. "gg"를 출력해야하는 조건은 간단하다. 벨만포드를 돌린 이후에 dst[e]가 INF인지를 확인해도 되며, 단순히 dfs나 bfs를 돌려도 된다. "Gee"의 조건은 더 생각해봐야 할 것이 있는데, 음수 사이클이 존재함은 물론, 음..
-
[16956] 늑대와 양BOJ 2022. 2. 5. 09:48
https://www.acmicpc.net/problem/16956 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 www.acmicpc.net 그래프랑은 별로 관련이 없다. 모든 빈칸에 울타리를 채워넣고, 'W'를 기준으로 상하좌우에 'S'가 있는지만 확인하면 된다. #include using namespace std; int n, m, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0}; char a[505][505]; bool vst[505][505]; int main(void) { ios_base::..