기로에 서다

문제 www.acmicpc.net/problem/5980 5980번: Corn Maze This past fall, Farmer John took the cows to visit a corn maze. But this wasn't just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both www.acmicpc.net 문제 풀이 알파벳으로 입력받는 Transport해주는 점들의 좌표를 따로 관리해주며 그 점들 간의 이동시에는 0 코스트가 들기 때문에 방..

문제 www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제 풀이 지나갈 수 있는 최소 값과 최대 값을 투포인터로 관리하며 시작점부터 bfs를 통해 끝점까지 가는 경우에 최대 값 - 최소 값을 갱신해준다면 $O(N^2*200)$으로 시간내에 답을 구할 수 있습니다. 코드 #include using namespace std; typedef pair pi; const int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,..

문제 www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 각 R줄 동안 C만큼의 문자열이 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제 풀이 1. 빙하가 녹는 시간마다 BFS를 돌릴 때, 최악의 경우 $O(R*C*max(R,C))$로 TLE가 난다. 2. 이에 빙하가 녹는시간을 BFS 한번으로 전처리한 후, 빙하가 녹는 시간에 대한 백조의 이동을 줄여보기로 한다. 3. 백조가 만날 수 있는 최소시간이 T초일 때, T-1초엔 녹지않은 빙하때문에 만날 수 없다는 점에서 "시간이 T일 때 백조가 만날 수 있는 가?" 라는 결정함수..

문제 www.acmicpc.net/problem/3673 3673번: 나눌 수 있는 부분 수열 양의 정수로 이루어진 수열이 주어졌을 때, 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 구하는 프로그램을 작성하시오. 예를 들어, 아래와 같은 수열의 부분 수열 중 4로 나누�� www.acmicpc.net 문제 풀이 1. n의 범위로 보아 연속된 부분수열의 합을 구하기 위해 누적합을 사용한다고 생각했습니다. 2. 시작점이 고정된 연속 부분수열의 합이 아니므로 구해야하는건 시작점을 s, 끝점을 e라 할 때, 구간[s,e]의 누적합이 (psum[e] - psum[s-1])%d ==0을 만족하는 (s,e)쌍을 찾는 것과 같았고, 이는 (psum[e] % d) == (psum[s - 1] % d)와 ..

문제 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 풀이 1. 항상 중앙 값을 구하기 위해 우선순위 큐 두 개를 아래의 그림과 같이 사용해서 입력받는 수를 관리하기로 한다. lpq = top쪽으로 갈수록 수가 커지는 max heap rpq = top쪽으로 갈수론 수가 작아지는 min heap 2. 입력받는 수(k)는 항상 두 힙중 하나에 들어가야하며 중앙값을 구하기위해 두 힙의 크기는 항상 같거나 lpq가 rpq보다 크기가 1큰 경우만..

문제 www.acmicpc.net/problem/17436 17436번: 소수의 배수 첫째 줄에 N(1 ≤ N ≤ 10)과 M(1 ≤ M ≤ 1012)이 주어진다. 둘째 줄에는 N개의 소수가 주어진다. 입력으로 주어지는 소수는 100보다 작거나 같으며, 같은 소수가 두 번 이상 주어지지 않는다. www.acmicpc.net 문제 풀이 m의 범위를 못보고 계속 int형으로 제출해 삽푼문제였다. 1. 우선 m에 대해 각각의 소수로 나눴을 때 나누어 떨어지는 개수를 모두 세어보면 m/p[0] , m/p[1] ...등이 있을 것이다. 2. 이 때 간단한 예시를 통해 생각해보면 중복으로 카운트되는 수들이 존재하는 걸 알 수 있다. m = 30, p[0]= 2 ,p[1] = 3 일 때, p[0]에선 2,4,6.....

문제 www.acmicpc.net/problem/16402 16402번: 제국 배성일력 73년, 대륙을 주름잡던 성일 제국은 무리한 정복 전쟁 끝에 멸망하게 되었다. 기회를 노리던 반란군들은 혼란을 틈타 제각각 왕국을 선포했고, 왕국들은 제국의 자리를 차지하기 위해 � www.acmicpc.net 문제 풀이 1. 유니온파인드로 집합을 관리하기 위해 각 국의 이름을 입력받은 후 파싱하여 map에 순으로 저장한다. 2. 위와 마찬가지로 각 국의 이름과 관계도 적절히 파싱한 후에 이기는 국가가 앞쪽으로 오도록 두 집합을 합쳐준다. 3. 합칠 때는 아래의 세가지 경우가 존재하고, 맨 위 두가지 경우는 같다고봐도 무방하다. (∵ 종주국 v의 부모는 pv) 종주국(u)이 종주국(v)을 이길 때 : u가 v의 속국으..

문제 www.acmicpc.net/problem/19576 19576번: 약수 가능 한 방법 중 하나로, a2를 12로, a3을 3으로 바꾸면 된다. www.acmicpc.net 문제 풀이 1. 약수관계를 생각해보면 1은 모든 수와 약수관계를 이루므로 와우매직을 사용하는 경우엔 1로 바꿔주면 된다. 2. 와우매직을 최소한으로 사용하기 위해선 기존의 수들이 최대한 많은 약수관계를 이뤄야하고, 이는 수들을 정렬했을 때 각 인덱스를 시작으로 해당 인덱스의 수와 다른 수들과의 약수관계를 이루는 길이를 구하고 그 중 최댓값을 n에서 빼주면 와우매직을 사용하는 최소횟수이다. 코드 #include using namespace std; int n, dp[5001]; vector a; int go(int cur) { i..

문제 www.acmicpc.net/problem/19588 b.first; } int main() { cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); cin >> n >> m; v.resize(n + 1), pxor.resize(n + 1), pxor2.resize(n + 1); for (int i = 1; i > x >> y; v[i] = { x, y }; } auto it = v.begin(); sort(it + 1, v.end(), cmp); for (int i = 1; i > q; while (q--) { cin >> a >> b; cout

문제 www.acmicpc.net/problem/19591 19591번: 독특한 계산기 숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. www.acmicpc.net 문제 풀이 1. 파싱 : 문자열을 숫자와 연산자로 파싱하는 과정이 까다롭지만 연산자가 나왔을 때, 연산자는 연산자대로 저장하고 그동안의 숫자들을 하나의 숫자로 묶어서 저장하면 쉽게 파싱할 수 있습니다. (첫 수가 음수일때 예외처리) 2. 자료구조 : 연산할 때 맨 앞과 뒤에 접근하므로 덱을 사용하여 숫자, 문자들을 관리할 수 있습니다. 3. 주어진 조건대로 연산자의 우선순..