-
[BOJ] 1413 : 박스 안의 열쇠
1413 : 박스 안의 열쇠 풀이 모든 열쇠를 얻으러면, 열쇠들 사이에 사이클이 생겨야한다. 우리에겐 k개의 폭탄이 있기 때문에, 이 열쇠들을 k개의 집합으로 나눠서 사이클을 만드는 경우의 수를 세면 된다. n개의 원소를 k개의 원순열로 분할하기 위해, 제1종 스털링 수라는 걸 사용해보자. s(n, k) = s(n-1, k-1) + (n-1)*s(n-1, k)라는 점화식이 나온다. gcd로 최대공약수를 구하고, 합으로 나눠주면 끝! 코드 #include <stdio.h> typedef long long ll; int n, m, i, j; ll dp[21][21] = { 1 }, div;...
-
[BOJ] 1412 : 일방통행
1412 : 일방통행 풀이 단방향과 양방향 간선이 섞여있는 그래프가 주어진다. 양방향 간선들을 모두 단방향 간선으로 바꾸었을 때, 사이클이 있는지 찾는 문제이다. 일단 솔루션부터 이야기하면, 양방향 간선들은 제껴두고 단방향 간선들만으로 사이클을 이루는지 검사하면 된다. 증명은 음… 증명이라고 하긴 뭐하지만 1->2, 1->3, 2->4, 3->4, 1-4, 2-3의 그래프를 가정하자. 단방향 간선들로 위상정렬을 하면, 1 2 3 4가 나올 것이다. 그리고 1-4와 2-3은 위상정렬 순서에 따라 단방향 간선으로 바꾸어주면 된다. (1->4, 2->3) 코드 #include <stdio.h> int n, vst[101], flag;...
-
[BOJ] 2667 : 단지번호붙이기
2667 : 단지번호붙이기 풀이 dfs를 돌려보자! 맵을 한 바퀴 쭉 돌면서, 아직 탐색하지 않은 단지를 만나면 dfs를 돌리자! 새로운 단지를 만날 때마다 단지 번호도 하나씩 늘려주자! 코드 #include <cstdio> #include <algorithm> const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; int n, k, cnt[26 * 26]; char arr[26][26]; void dfs(int x, int y) { arr[x][y] = '0', cnt[k]++; for (int i = 0; i < 4; i++) { int nx...
-
[BOJ] 11779 : 최소비용 구하기 2
11779 : 최소비용 구하기 2 풀이 다익스트라를 쓰면 된다! 대신 trace(=trc)배열을 만들어서 노드 i가 어디서 왔는지 저장해주고, 나중에 역으로 따라서 출력하면 된다. 코드 #include <stdio.h> #include <vector> #include <algorithm> #include <queue> using namespace std; const int n_ = 1e3 + 3; const int INF = 1e9; struct edg { int idx, dst; edg(int idx, int dst) : idx(idx), dst(dst) {} bool operator <(edg A)const { return dst > A.dst; } }; int n, m, trc[n_],...
-
[BOJ] 11438 : LCA2
11438 : LCA2 풀이 이번엔 naive가 아닌 풀이! 이전의 naive한 풀이에서, 우리는 최악의 경우에 n번의 노드를 하나씩하나씩 올라가야했다. 하지만 이를 log(n)으로 줄일 수 있다! pnt[i][j] = i번 노드의 2^j번째 조상으로 두고 풀면 된다. 트리의 깊이를 구할 때 2^j번째 조상을 구해두자. tmp = anc[i][j-1]일 때, anc[i][j]는 anc[tmp][j-1]과 같다. 즉, i의 2^j번째 조상은 2^(j-1)번째 조상의 2^(j-1)번째 조상과 같다는 의미이다. i의 2^3=8번째 조상은 2^2=4번째 조상의 2^2=4번째 조상과 같다. naive한 코드에서 2^j를 도는 동작만 추가해주면 어렵지 않게(?) 훨씬 빠르게(!)...
-
[BOJ] 11437 : LCA
11437 : LCA 풀이 naive한 풀이! dfs 먼저 돌려서 각 노드마다 깊이를 구해준 뒤, u, v 두 노드 중 더 큰 노드의 깊이를 끌어 올려준 다음에 두 노드에서 동시에 하나씩 올라가며 같은 노드에서 마주칠 때 까지 올려주면 된다. 코드 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; const int n_ = 5e4 + 3; int n, m; int dph[n_], pnt[n_]; vector<int> gph[n_]; inline void dfs(int now, int cnt) { dph[now] = cnt++; for (auto...
-
[BOJ] 13306 : 트리
13306 : 트리 풀이 엣지를 제거하면서 union find를 하려면 TLE가 난다. 문제를 거꾸로 생각하자. 원래의 문제는 간선이 모두 이어진 상태에서 하나씩 제거하는 형태이다. 그렇다면 역으로 간선을 다 끊어놓고 쿼리를 뒤에서 부터 돌면 되지 않을까?! 간선을 하나씩 이어주면서 union find를 돌리게 되면 빠르게 답을 구할 수 있다. 발상의 전환이 조금 어려운 문제인 것 같다. 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 2e5 + 3; int n, q; int gph[n_], pnt[n_], q1[n_ * 2],...
-
2017 선린 봄맞이 교내대회 풀이
2017 선린 봄맞이 교내대회 풀이 문제 링크: https://www.acmicpc.net/contest/view/222 뭔가 야심차게 HARD 난이도(교내대회 기준)로 낸 문제들이 여럿 있었는데 생각치 못하게 엄청 쉽게 풀려서 당황스러웠다 ㅠㅠ A. 욱제는 효도쟁이야!! 14487 : 욱제는 효도쟁이야!! 풀이 각 마을간의 이동거리가 주어지고, 모든 마을을 순회할 때 그 이동거리의 합을 최소로 만드는 문제이다. 모든 이동거리의 합에서 최대 이동거리를 빼주면 된다. 코드 #include <stdio.h> int n, tmp, sum, i, a; int main() { scanf("%d", &n); for (i = 0; i < n; i++)...
-
2017 선린 봄맞이 교내대회 안내
2017 선린 봄맞이 교내대회 안내 안녕하세요! 대회의 세부사항에 대해서 안내 해드립니다. 일시: 2017년 4월 9일 일요일 14:00 ~ 19:00 5시간 장소: acmicpc.net 후원: 스타트링크 상품: 1등 치킨 기프티콘 출제: wookje, leehun456 한글, 12문제, 3인 이하의 팀전 Open Contest 동시 운영 4월 6일 오후에 대표자 이메일로 팀 전용 계정을 발송해드립니다. 반드시 확인하시고 4/7~4/8 사이에 이 링크에 있는 2017 선린 봄맞이 교내대회 예비소집에 참여하셔서 채점환경 등을 확인해주시기 바랍니다. 아래의 테이블은 참가자 정보입니다. 누락되거나 잘못된 정보는 연락해주시면 즉시...
-
[BOJ] 11052 : 붕어빵 판매하기
11052 : 붕어빵 판매하기 풀이 dp[i] = 붕어빵 i개를 팔았을 때의 최댓값 dp[i] = i-j번째 최댓값 + j개 세트의 가격 코드 #include <stdio.h> int n, i, j, a[1001], dp[1001]; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &a[i]); for (i = 1; i <= n; i++) for (j = 1; j <= i; j++) if (dp[i] < dp[i - j] + a[j]) dp[i] = dp[i - j] + a[j];...