문제가 처음에 이해하기 어려웠다3과목을 시험보는데 A가 B보다 모든과목을 잘보면 '대단한 학생'C라는 학생보다 '대단한 학생'이 한명도 없다면 '굉장한 학생' 이다 처음에 세그먼트 트리를 2개 만들어서 비교하려했는데 실패했다 ㅎㅎ 3과목이라 조건이 3가지이기 때문에 아이디어를 잘 떠올려야 한다 문제를 푸는 방법은1. 첫번째 등수 기준으로 정렬을 한다2. 세그먼트 트리를 만든다. 이 때 트리는 최소값 트리다3. 트리의 i번째에는 두번째 과목을 i등한 사람의 3번째 과목 등수를 넣는다4. 0~n-1까지 for문을 돌며 두번째 과목 등수까지의 값이 3번째 등수 값보다 크다면 이학생은 굉장한 학생이다! 이렇게 3가지 조건을 다 만족시켜주게 트리를 만들면 되는데.... 어렵다! 소스코드123456789101112..
N 개의 정점이 있고 0번에서 1번 까지의 최단거리를 구하는 문제다이 때 가 간선은 가중치를 2개 가진다.최단거리는 0번부터 1번 까지의 1번가중치 합 X 2번가중치 합 이다. 처음에 완탐인줄알고 백트래킹했는데 생각해보니 최악일 때 20!이다..! 문제를 푸는방법은 그냥 다익스트라를 쓰면 된다 ㅋㅋpq에 (가중치1의 합, 가중치2의 합)을 추가로 넣어가면 쉽게 풀 수 있다! 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include #include #include using namespace std;int n, ans = 1e9;bool check[22]..
X에서 출발해 X로 돌아올 수 있는지 없는지 판단하는 문제다Cycle이 있으면 안되는 문제다.하지만 양방향 간선끼리의 Cycle은 방향을 알아서 지정하면 되므로 문제가 안된다..! 따라서 양방향인 간선들은 무시하고 단방향인 간선들로 그래프를 그린다그리고 Cycle을 찾으면 된다! Cycle을 찾는 함수를 사용해도 괜찮고 플로이드를 써도 괜찮다! 소스코드(Cycle detect)12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include using namespace std;int n, arr[111][111], check[111];vector Graph;bool isCycle(int..
더 게임 오브 데.. 스.. 어렵다...K개 간선을 지나서 A->B로 갈 수 있다면 death 아니면 life다.생각이 안나서 폭풍도움을 받고 A^k을 하고 A[i][j]가 1이라면i->j라는 사실을 알았따... 생각해보니까 이산수학에서 transitive closure로 나온 것 같다.길이가 n인 path가 있으려면 A^n해서 확인했었다...!잘 기억해둬야겠다.. 행렬곱 n^3 * K(1,000,000) 이니까 정직하게 곱하면 시간안에 못푼다..!그래서 A^k를 log만에 구하는 방법으로 구현해야한다! 하지만 내 소스는 결국 틀렸다 ㅎㅎ..60..%..백준의 코드를 보며 공..부..하고.. 풀었다..!코드 깨끗하게 잘짜는 연습 해야겠다 ㅎㅎ 소스코드123456789101112131415161718192..