기로에 서다

문제 https://www.acmicpc.net/problem/13018 13018번: 특이한 수열 첫째 줄에 n, k (1 ≤ n ≤ 10^5, 0 ≤ k ≤ n)가 주어진다. www.acmicpc.net 풀이 아래와 같이 몇 가지를 관찰하여 해결할 수 있습니다. 1. 1 ~ n까지의 수를 순서대로 둘 때, 1을 제외한 모든 수는 gcd(i, A[i]) > 1을 만족합니다. 따라서 주어진 조건을 만족하는 최대 k값은 n - 1이므로 n == k인 경우 불가능합니다. 2. gcd(i, A[i]) > 1을 k개의 수가 만족한다는 것은 gcd(i, A[i]) > 1을 n - k개 만족하지 않는다는 것과 같습니다. 1에서 순서대로 놓은 수들은 1을 제외하고 모두 gcd(i, A[i]) > 1을 만족하므로 편의..

문제 https://www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 풀이 1. 0번부터 n - 1번까지 중앙 정점을 옮겨가며 매번 거리를 계산하는게 아니라 0번 정점과 그 외 정점사이의 거리를 구한 후, 중앙 정점을 옮길 때마다 추가/감소되는 비용만 구하면 최소거리인 중앙정점을 구할 수 있습니다. 2. 정점을 옮길 때마다 추가/감소되는 비용은 정점과 연결된 간선들의 개수와 관련이 있고, 이는 dfs를 돌려 연결된 간선개수를 찾을 수 있습..

문제 www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 풀이 낼 수 있는 카드를 정렬해둔 후, upperbound를 통해 낼 카드 번호를 바로 구할 수 있을 것 같지만 낸 카드는 버리기에 사용한 카드의 유무를 저장하는 배열을 사용해 항상 사용하지 않은 카드를 내는 식으로 해결할 수 있습니다. $O((m + k)logm)$ 코드 #include using namespace std; int n, m, k, x,..

문제 www.acmicpc.net/problem/7045 7045번: Tree Cutting After Farmer John realized that Bessie had installed a "tree-shaped" network among his N (1

문제 www.acmicpc.net/problem/5867 5867번: Scrambled Letters Farmer John keeps an alphabetically-ordered list of his N cows (1 > n; miv.resize(n), mav.resize(n); for (int i = 0; i > s; sort(all(s)); miv[i] = s; low.push_back(s); reverse(all(s)); mav[i] = s; high.push_back(s); } sort(all(low)), sort(all(high)); for (int i = 0; i < n; i++) { p1 = lower_bound(all(high), miv[i]) - high...

문제 www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 풀이 1. 조는 친구들을 우선 체크한 후, 출석 번호를 받은 친구들의 배수마다 출석했다고 체크를 하는데 조는 친구들은 무시하고 넘어가면 됩니다. 2. 이 때 구간질의마다 학생 수를 세면 시간초과가 나기 때문에 미리 누적합 배열을 저장해놓고, [s, e] 구간의 합에 대해psum[e] - psum[s - 1]을 출력하면 해결할 수 있습니다. 코드 #include ..

문제 www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 풀이 1. W가 소문자 알파벳으로만 이루어졌으므로 문자열 내에서 알파벳들의 위치를 담는 알파벳 벡터를 만들어 각각의 위치들을 담아줍니다. 2. 알파벳 벡터를 순회하며 크기가 K이상인 것들에 대해서 시작 인덱스를 st라 하면 끝은 st + k - 1까지 원소들을 K개씩 검사합니다. 3. 이 때 문제에서 요구하는 정확히 K개 문자를 포함하는 연속 문자열은 결국 w를 구성하는 연속 문자열[st, st + k..

문제 www.acmicpc.net/problem/20436 20436번: ZOAC 3 첫 번째 줄에는 두 알파벳 소문자 sL, sR이 주어진다. sL, sR은 각각 왼손 검지손가락, 오른손 검지손가락의 처음 위치이다. 그 다음 줄에는 알파벳 소문자로 구성된 문자열이 주어진다. 문자열의 www.acmicpc.net 풀이 1. 각기 다른 자판의 위치를 좌표로 저장하고 왼쪽 손이 닿을 수 있는 위치, 오른쪽 손이 닿을 수 있는 위치를 구분하여 손의 위치와 자판의 거리만큼 더해가면서 해결할 수 있습니다. 2. 거리와 상관없이 문자를 누르는 횟수는 문자열의 길이와 같습니다. 따라서 답은 거리의 합에 문자열의 길이를 더해준 것입니다. 코드 #include using namespace std; typedef pair..

문제 www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 1. 파이프의 가능한 경로를 찾기위해서 위부터 아래로 진행방향을 고정하고 끝점까지 도착 할 수 있는지의 여부를 체크하는 dfs를 진행합니다. 2. 위의 그림에서 파이프의 경로가 되는 빨간점에서 파란점들로 가는 상황에 대해서 생각해보면 아래와 같은 결론을 낼 수 있습니다. 1번 빨간점이 다음 열로 이동할 때 1번 파란점이아닌 2번 파란점으로 이동한다면 2번 빨간점이 이동할 수 없습니다. 따라서 윗점에서 파이프의 경로가..

문제 www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 풀이 1. 간단하게 생각해본다면 시작 점에서부터 BFS를 돌려 "왼쪽 위 점에서부터 오른쪽 아래 점까지 1이 포함되어 있는가?"를 확인하며 진행하면 될 것 같지만 $O(n*m*h*w)$로 시간 초과가 납니다. 2. "해당 점에서 부터 오른쪽 아래 점까지 1이 포함되어 있는가?"를 연산하며 중복된 칸을 계속 탐색하므로 이를 막기 위해 dp를 사용합니다. 이때 상태 정의는 "dp[i]..