뉴비의 PS 낙서장

https://www.acmicpc.net/problem/1665 1665번: 화물열차 첫째 줄에는 화물 열차 A에 연속적으로 컨테이너가 놓여 있는 구간의 개수 N이 주어진다. 이어 N줄에는 Xi와 Yi (Xi ≤ Yi)가 공백을 사이에 두고 주어지는데 이는 화물 열차 A의 Xi칸부터 Yi칸까지 컨 www.acmicpc.net 이렇게 총 5개의 상황이 벌어질 수 있고, 두 시작점이 만나는 시점부터 컨테이너가 만나는 칸 수가 늘어나다가, A의 시작이 B의 끝을 만나거나, A의 끝이 B의 시작을 만나는 경우가 생기면 칸 수가 유지되다가 하락한다. 그러다 두 끝점이 만나는 시점부터는 컨테이너가 만나는 칸 수가 0이 유지된다. 이 기울기 함수들을 누적합으로 관리해서 최대로 컨테이너 끼리 만나는 칸 수가 몇인지 ..

https://www.acmicpc.net/problem/1616 1616번: 드럼통 메시지 첫째 줄에 자연수 K, M이 주어진다. K는 2이상, M은 1이상인 자연수이다. 항상 KM ≤ 10,000,000을 만족한다. www.acmicpc.net 일단 길이가 \(M-1\) 개로 이루어진 모든 메시지에 대해 다음 메시지로 나올 수 있는 메시지들에 대해 간선을 이어준다. 이때, 간선의 가중치에는 추가되는 수가 부여된다. 아래의 경우는 \(K = 2\), \(M = 3\) 인 경우다. 여기서 오일러 경로를 사용해 지나쳐온 모든 간선들의 가중치를 저장해둔다. 저장된 값은 \(11101000\)이고, 놀랍게도, 저장된 메시지는 우리가 찾고자 하는 답이 된다. 시간 복잡도는 \(O(K^{M-1}*K)\) = \(..

www.acmicpc.net/problem/10169 10169번: 안전한 비상연락망 입력의 첫 줄에는 마을의 수 N (2 ≤ N ≤ 100,000)과 도로의 수 M (2 ≤ M ≤ 300,000)이 자연수로 주어진다. 각 마을은 1번부터 번호가 붙은 것으로 생각한다. 이후 M 개의 줄에는 각각 3개의 자연수가 주 www.acmicpc.net 도로 하나가 없어졌을때마다 mst를 구하는 문제다. 일단 두가지 경우로 나눌 수 있는데, i) 기본 mst에 포함되지 않는 도로인 경우 ii) 기본 mst에 포함된 도로인 경우 i)에 대해서는 답이 변하지 않는다는 것을 알 수 있다. 이제 ii)에 대한 처리가 문제인데, 일단 mst로 만들어진 도로로 트리를 만든다. 검은색 : mst에 포함된 도로, 빨간색 : 포함..

www.acmicpc.net/problem/18913 18913번: Graph Coloring You are given a tournament, represented as a complete directed graph (for all pairs $i,j$ of two different vertices, there is exactly one edge among $i \to j$ and $j \to i$), with $n \leq 3000$ vertices. You need to color its edges into $14$ colors. There www.acmicpc.net 내가 푼 문제중에 재밌던 문제의 풀이를 블로그에 올린다. 그래프의 간선들에 \(a\)~\(n\)의 색을 매길건데, 어떤 경로 \(x..

일단 이 문제가 왜 다4인지 모르겠다. 풀이 각 좌표 마다 가장 가까운 냄새나는 사람과의 거리를 알아두면, 다익스트라 한번이면 해결된다. 가장 가까운 냄새나는 사람과의 거리는 BFS 돌면 된다. (각 냄새나는 사람마다 퍼지는 식) 솔직히 너무 간단해서 골1 정도 되는거 같다. 빨리 꿀문제를 풀러 가보자! + 이 풀이는 어떤 지인분이 정해가 아닌 꼼수같은 풀이라고 합니다. (하지만 반례가 없ㄷ..) 코드 #include #define x first #define y second using namespace std; typedef long long ll; typedef pair pi; typedef vector vec; int n,m,k,sx,sy,ex,ey; int nx[8] = {1,0,-1,0,1,1,..

흰색으로 만들기 문제다. 17302번: 흰색으로 만들기 첫 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 2,000) 다음 줄부터 N개의 줄에 걸쳐 각 행의 상태를 나타내는 길이 M의 문자열이 주어진다. 모든 문자열은 'B'와 'W'로 이루어져 있다. i 번째 줄, j 번째 문자� www.acmicpc.net 관찰을 하나 해보자. 2번 동작에서 3번 동작으로 바꾸면, 가운데 하나만 색이 반전 된다는 것을 알 수 있다. 모두 2번 동작을 한다. 그리고 검은색 타일에 대해서 3번 동작으로 바꿔주면 모두 하얀색 타일로 바뀐다. #include #define x first #define y second using namespace std; typedef long long ll; typedef long doub..

세 용액은 여러가지 풀이가 있습니다 1. 트리를 이용한 풀이 2. 이분탐색을 이용한 풀이 3. 양방향 탐색을 이용한 풀이 이 블로그에서는 양방향 탐색을 이용한 풀이 입니다. \(N\) 번을 돌면서 하나를 고정시키고 나머지 두개를 양방향 탐색으로 찾는 풀이입니다. 시간복잡도는 \(O(n^{2})\) 입니다. #include using namespace std; /// 풀이 : 하나를 고정시키고 나머지 두개를 양방향 탐색으로 찾을거에요! int n; long long a[5005]; int main() { cin >> n; for(int i = 1;i > a[i]; } sort(a+1,a+n+1); /// 정렬을 해야 가능해요! int idx1 = n-2,idx2 = n-1,idx3 = n; /// 여기에 ..

Mo's algorithm 을 사용하는 문제다. 와아아아아아아앙 짝짝짝짝 각 숫자마다 list로 관리하면서 (dq[i].front-dq[i].back) 의 값이 숫자 i 의 최대 길이이다. 이제 이 숫자 i의 최대길이를 O(k) 가 아닌 O(sqrt(K)) 에 구해아 한다. 이 방법은 최대길이를 관리하는 버킷을 만들어서 sqrt(K) 개로 쪼갠다음 각 구간을 관리한다. 이러면 제일긴 길이 를 찾는방법을 O(sqrt(K)) 만에 구할 수 있다. 자세한건 코드를 보자. #include using namespace std; list dq[300005]; int n,k,Q,val,sz; int ans[300005],a[300005]; int b[300005],cnt[5000005]; struct Query { ..

\(DP[N] : N\)번째 징검다리를 건널때 나올 수 있는 경우의 수 라고 잡아보면 \(DP[N] = DP[N-1]+DP[N-2]+...+DP[1]\) 이라는 식이 나오는데 \(DP[N-1] = DP[N-2]+DP[N-3]+...+DP[1]\) \(DP[N-2] = DP[N-3]+DP[N-4]+...+DP[1]\) . . . \(DP[1] = 1\) 이제 \(DP[1]\) 부터 \(DP[n-1]\)을 \(DP[n]\) 의 식에 대입해 보면 \(DP[N] = 2^{1}(DP[N-2]+DP[N-3]+...+DP[1])=\) \(2^{2}(DP[N-3]+DP[N-4]+...+DP[1])\) \(= 2^{3}(DP[N-4]+DP[N-5]+...+DP[1])... =2^{N-2}DP[1]\) 가 나옵니다. DP..

알고리즘은 그리디 입니다. 일단 제일 가격이 낮은 숫자들로 최대한 채웁니다. 이때, 0 이 제일 싼 가격이면 그 다음으로 싼 가격의 숫자를 맨 앞에 놓고 그 뒤에 0을 쭉 붙입니다. 그러면 쓰고 남는 돈이 있는데 이 돈으로 최대한 큰 수로 바꿉니다. 각 숫자에 대해 몇개씩 살 수 있는지 나오는데 이 숫자들을 내림차순으로 나열하면 제일 큰 숫자를 만들 수 있습니다. 제가 쫌 코드를 드럽게 짜기 때문에 풀이 이해용으로만 보시기 바랍니다. #include using namespace std; typedef long long ll; int n,pl,End; ll k,x,co[15],ch[15],tmp[15]; struct Money { ll cost; int num; }a[15]; bool cmp(Money p..