www.acmicpc.net/problem/1637 1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 가능한 입력이 MAX_INT 까지이므로 하나하나 개수를 세면 시간을 초과합니다. log n으로 찾을만한 이분 탐색을 사용하려 했지만 아이디어가 떠오르지 않아 www.acmicpc.net/board/view/18341 글을 참고했습니다. f(x) 를 입력에 대해 x 이하의 수의 개수라고 합니다. x 이하의 수의 개수는 i번째 입력에 대해 a>x 일 때 0개, ..
www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 설계도가 주어져있을 때 최소 문을 몇 개 열어 탈옥시킬 수 있는 지 구하는 문제입니다. 상근이가 감옥 바깥을 자유롭게 돌아다니므로 상근이가 (0,0)에 있는 죄수라 가정하고, 감옥 바깥을 모두 ' . '으로 채워줍니다. 특정 위치에 3명의 죄수가 그 위치에 도달할 수 있다면, 그 위치를 지나는 경로는 3명 모두에게 존재하는 것입니다. (이걸 처리 안 해서 계속 틀리고 있었다....) 해당 죄수들에 대해 죄수들이 해당 위치로..
www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 수빈이와 동생의 위치가 주어져있을 때 수빈이가 최소 몇 번만에 동생한테 갈 수 있는지 구하는 문제입니다. 수빈이가 이동하는 경로는 현재 위치 +1 , -1, *2 인데, *2로 이동하는 경우는 0초, 나머지는 1초가 걸립니다. 현재 위치가 N일 때, 이동 가능한 위치는 N+1, N-1, N*2 3가지 이므로 3가지 위치에 대해 bfs를 진행하면 됩니다. 주의할 점은 이미 이동했..
www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net LCA (최소 공통 조상) 문제입니다. 최소공통조상이란, 트리가 주어져 있을 때 가장 가까운 공통 조상을 의미합니다. (자식 노드에 자기 자신 포함. (루트)1-2-3의 연결이 있을 때, 2,3 노드의 최소공통조상은 2번 노드) LCA 알고리즘은 다음과 같습니다. 1. 모든 노드에 대해 깊이를 구한다. 2. 모든 노드에 대해 2^i 번째 부모를 구한다. 3. ..
www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 선거 구역을 최대한 공평하게 나누는 게리맨더링 문제입니다. 주어진 그래프에서 선거 구역을 2군데로 나누는데 나누어진 구역들은 모두 1개 이상이어야하고, 모두 이어져 있어야합니다. 풀이 1. 가능한 모든 조합을 구한다. 단, 1개 이상 원소 포함 ({1,2,3},{4,5,6} 계산 후 {4,5,6},{1,2,3} 계산하는 것과 같이 중복 내용이 포함되지만, worst case가 n=10으로 작은 경우이기에 중복 제거 안해도 될 거 같..