https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질 시리즈의 최종판이다. 이 문제는 다른 문제들과 달리, 동생의 위치에 포커싱을 맞춰야한다. (1초에는 1만큼 움직이고, 2초에는 2만큼 움직인다) (즉, 움직인 거리로 시간을 대체할 수 있다!) 만약 수빈이가 14초에 x라는 지점을 방문했다고 하자. 그런데 동생이 20초에 그 x지점을 방문했다. 그럼 수빈이와 동생은 20초만에 만날 수 있는 것이다. 라..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질1에 이은 문제이다. 숨바꼭질1은 최단경로를 찾아 루트부터 해당 노드까지의 거리(= 가장 빠른 시간)를 출력하고 바로 종료했다면, 이 문제는 큐가 빌 때 까지 모든 경우를 다 탐색해주면 된다. 물론, 가장 빠른 시간이 찾아지면 그보다 시간이 오래 걸리는 경로는 필요없으므로 트리가 한단계 더 깊어지면 멈춰준다. 이것은 약간의 트릭이다. 멈추지않고 찾아도 ..
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 간단한 bfs문제이다. 큐에는 방문하는 숫자정보와 누적 방문 횟수를 저장해주면 된다. 그리고 현재 방문하는 숫자 - 1, 숫자 + 1, 숫자 x 2를 방문해주면 된다. 총 3가지 경우에 대해 모두 방문해보는 것이다. #include using namespace std; typedef unsigned long long ull; int n,k,ans; queue q; boo..
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 오랜만에 푼 구현 + 브루트 포스 + 백트래킹 문제이다. 문제 자체는 크게 까다롭지 않지만, 백트래킹에서 고민을 좀 많이 하였고 결국 다른 글을 참고하게 되었다..(시무룩) 1. 입력을 받는다 (CCTV가 나오면 해당 좌표를 벡터에 담아준다!) 2. 완전 탐색을 실시한다. 3-1. 만약 모든 CCTV를 확인하여, 감시 구역을 정했으면 사각지대의 수를 세서 최솟값을 저장한다. 3-2. 아..
https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 문제가 한번에 이해가 안될수도 있으니,, 꼼꼼히 읽어보셔야 한다. 우선, 이 문제는 누가봐도 정렬과 그리디 알고리즘이다. 이 문제를 풀 때 3가지 key point가 있다고 생각한다. 1. 음수부분과 양수부분을 구별 (음수의 개수 세기) 2. m개의 책을 들고 다닐 수 있으므로 m칸씩 이동 3. 맨 끝 값(제일 작은 음수, 제일 큰 양수) 중 절댓값이 더 큰 것을 마지막에 방문 (= 되돌아올 필요 없으..
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 간단한 트리 + dfs 문제이다. 그런데 이 문제는 문제를 잘 읽어야한다. 이진트리도 아니며, 입력으로는 노드가 순서대로 주어지는 것이 아니라 노드의 부모가 주어진다. 그리고 꼭 0번 노드(첫 입력)가 root노드인 것은 아니다! -1(부모가 없는 경우)이 입력으로 들어올 때 해당 노드가 트리의 root이다. 예제 1번이 문제의 그림과 동일하므로 천천히 비교해보시길 바란다. 우선 트리를 입력..
