결국 오고야 마는 것들

위상정렬인데, 특정 건물을 짓기 전 소요되는 가장 긴 시간을 기준으로 완성 시간을 구해나가면 된다. 개인적으로 1766이나 2252번 보다 더 어려운 것 같은데 난이도가 더 낮아서 의아하다... 두 문제가 overrated된 느낌 #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; vector adj[501]; int indegree[501], arr[501], cost[501]; int n; void input() { fastio; cin >> n; for(int i = 1; i > arr[i]; int req; while(cin >> req) { if(req == -1) break; ++indegree[i];..

혼내주기 2021. 8. 1. 22:39

ps 처음 공부할 때 꾸역꾸역 블로그 찾아가면서 풀고 이해를 못했던 기억이 있는 문제였는데, 지금 풀어보니까 이렇게 쉬울 수가 없다... 스택에 넣을 때 마다 현재 숫자보다 작은 숫자를 다 pop해주면 되는 문제. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int arr[1000001]; int n; void input() { fastio; cin >> n; } int main() { input(); stack stk; for(int i = 0; i > num; while(!stk.empty() && stk.top().first < num) { arr[stk..

혼내주기 2021. 8. 1. 22:37

작년에 교내 SW육목경진대회에 나가면서 minimax 알고리즘과 alpha beta pruning 알고리즘을 공부했었는데, minimax 알고리즘으로 푸는 문제였다. 근우의 차례에는 값이 최대가 되도록, 명우의 차례에는 값이 최소(명우의 최선의 플레이)가 되도록 구현하면 된다. 교내 대회를 나간 경험이 ps에서 도움이 된다니... 이런 경험이 공부하면서 즐거운 시간들 중 하나인 것 같다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int arr[1000], cache[1000][1000]; int n; void input() { cin >> n; for(int i = 0; i < n; ++i) { cin..

혼내주기 2021. 8. 1. 22:36

dp문제인데 원형으로 돌아가는 bounds 처리를 잘못해서 헤맸다. 문제를 구상할 때 어떻게 풀어야 할지 뿐만 아니라 corner case들도 충분히 생각해서 접근하는 연습을 해야지 장기적으로 문제 푸는 속도를 올릴 수 있을 것 같다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; ll cache[2000][2000]; int arr[2000]; int n; void input() { fastio; cin >> n; for(int i = 0; i > arr[i]; } int cFrom(int from) { return from-1 == -1 ..

혼내주기 2021. 8. 1. 22:35

이중 포문을 nm이 아니라 nn으로 돌다가 오래 헤맸다... 벽을 놓는 dfs를 돌릴 때 매번 0,0에서 시작하지 않고 다음 지점부터 시작하면 시간이 많이 단축된다. 요종도 #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0 , -1}; queue viruses; bool visited[8][8]; int arr[8][8]; int n, m, ans = 0, walls = 0; void input() { fastio; cin >> n >> m; for(int i = 0; i < n; ++i) { for(int j = 0; j <..

혼내주기 2021. 8. 1. 22:32

아이디어는 어렵지 않았는데, 모든 경우의 수를 문자열로 만드니 stoi 함수가 빈 문자열일 때 에러가 나서 고치는데 꽤나 고생했다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; string target; int n, answer; bool broken[10]; void input() { fastio; int numBroken, num; cin >> target >> numBroken; n = stoi(target); for(int i = 0; i > num; broken[num] = true; } } void d(string& num) { for(int i = ..

혼내주기 2021. 8. 1. 22:31

우큐를 두개 만들고 값과 index를 넣는다. D 연산의 경우 해당 인덱스가 유효하지 않다고 표시해 반대 우큐에서도 거르면 된다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int t, n; void input() { fastio; cin >> t; } int main() { input(); int num; char s; while(t--) { cin >> n; priority_queue minHeap; priority_queue maxHeap; vector valid(n, true); int cnt = 0; for(int i = 0; i > s >> num; if(s ==..

혼내주기 2021. 8. 1. 22:30

종만북으로 한창 공부할 때 힘들게 풀었었는데, 다시 풀어도 마냥 쉽지는 않은 문제. dp를 이용해 중복 계산이 없도록 하면서 모든 순서대로 계산한 결과의 최솟값을 재귀적으로 찾으면 된다. 11066 파일 합치기 문제와 아주 유사하다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int arr[500][2], cache[500][500]; int n; void input() { fastio; cin >> n; for(int i = 0; i > arr[i][0] >> arr[i][1]; } int min(int a, int b) {return a > b ? b : a;} int df..

혼내주기 2021. 8. 1. 22:29