https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 처음에는 먼저 일어난 사건을 부모, 나중에 일어난 사건을 자식으로 생각하고 그래프 그려서 dfs나 bfs 써도 널널할 거 같았지만 중복 탐색이 많아 플로이드 워셜을 이용해 풀었습니다. 플로이드 워셜은 원래 모든 점에서 모든 점으로의 최단, 최대 경로를 찾는 것이지만, 이를 응용하여 경로 유무만 파악합니다. O(n^3) 이지만 n j 로 가는 경로가 존재할 때 true, 아니면 false로 ..
https://www.acmicpc.net/problem/3372 3372번: 보드 점프 N × N 게임 보드에 양의 숫자들이 적혀있다. 목적은 왼쪽 위에서 오른쪽 아래까지 규칙에 맞게 점프를 해서 가는 것이다. 숫자들은 현재 점에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 www.acmicpc.net 마지막에만 0 들어오는 줄 알고 예외처리 안 했더니 메모리 초과가 뜹니다. N*N 맵에 입력으로 주어지는 숫자만큼 오른쪽 혹은 아래로 이동가능할 때 왼쪽 위에서 오른쪽 아래로 이동가능한 경로의 수를 구하는 문제입니다. dp 문제로 쉽게 접근할 수 있지만 주의할 점은 총 경우의 수가 2^63보다 클 수 있기에 long long으로도 커버가 안 되므로 string으로 덧셈을 구현해서 풀었습니다. dp ..
https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net k번을 전부 돌려야 해서 조금 까다로운 문제였습니다. 1,000,000 이하의 수이므로 사실상 6자리라 보면 스왑하는 경우는 총 6C2=15, 10번 진행하므로 나올 수 있는 전체 경우는 15^10개입니다. 하지만 이를 모두 확인하는 것은 시간초과가 뻔하므로 (15^10 => 얼추 2^40 정도) 중복을 피해야합니다. (ex. 111 은 어떤 경우라도 스왑 시 111 이런 경우를 최소화시켜야 한다.) bfs와 set을 이용해 풀었습니다. 각 라운드 (k번 라운드) 마..
https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 주어진 입력으로 중위 순회가 되도록 만드는 문제입니다. 중위 순회 : 트리를 왼쪽 자식 -> 부모 -> 오른 자식 순으로 탐색 모든 depth에 자식을 2개씩 갖는 포화 이진 트리이므로 (문제 제목은 완전 이진 트리이지만 문제에 2^k-1 개 노드 갖는다고 함) 인터벌의 가운데가 부모가 되며 depth를 1씩 올리며 재귀를 돌면 됩니다. 코드는 다음과 같습니다. #incl..
https://www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 원형이라는 조건 때문에 조금 까다로운 문제였습니다. 우선 입력으로 들어오는 애들을 a > b 인 경우 b b2.last; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; cin >> m; long long max_len = 0; int max_..