본문 바로가기

전체 글

BOJ)2252 줄 세우기 문제: icpc.me/2252 N명이 학생이 주어지고 두 학생의 키를 비교한 M개의 정보가 주어질 때 줄을 세운 결과를 출력하는 문제이다. 우리는 두 학생의 우선관계를 방향 그래프를 이용하여 설정해준 뒤 topology를 구해주면 된다. 즉 DFS를 돌리면서 먼저 끝나는 순서대로 스택에 저장해준 뒤 하나씩 뽑으면서 출력해주면 답을 얻을 수 있다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include #include #define MAX_N 32000using namespace std;vector vt;stack st;int n, m, x, y, visited[MAX_N + 1];void dfs(int .. 더보기
BOJ)1561 놀이 공원 문제:icpc.me/1561 M개의 놀이기구를 순서대로 타는데 각각의 놀이기구의 운행시간이 주어질 때 마지막 아이는 몇번째 놀이기구를 타게되는지 출력하는 문제이다. 우리는 파라메트릭 서치를 이용하여 N명의 인원이 놀이기구를 탑승하는데 걸리는 시간 T를 구할 수 있다. T를 구했다면 T-1초동안 놀이기구를 탄 아이 수를 쉽게 구할 수 있고 이를 K라 했을 때 우리는 O(M)만큼 탐색하여 앞으로 O(N-K)번째로 타게 될 놀이기구의 번호를 구하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include using namespace std;typedef long long ll;ll n, m,.. 더보기
한문제를 풀면 4문제를 해결 가능 히스토그램에서 가장 큰 직사각형 문제는 매우 유명한 문제다. 근데 이 문제 한문제를 풀면 BOJ에서 무려 4문제를 약간의 수정을 통해 AC 받을수 있다. 히스토그램 Maximal Area 무서운 아르바이트 정말 꿀문제인거 같다 더보기

티스토리툴바