https://www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 구역의 움직임을 그래프로 표현한 뒤 그래프를 SCC(강한 연결 요소)로 표현하여, SCC로 표현된 요소(Component)들 간의 그래프를 다시 만들고, SCC의 요소들 간의 그래프는 DAG라는 특징을 이용해 SCC 요소로 만든 그래프에서 indegree가 0인 요소가 1개만 존재하는지 확인하는 방법으로 모든 구역에 도달하는 시작 구역이 존재하는지 확인했다. 그리고 indegree..

https://www.acmicpc.net/problem/9007 9007번: 카누 선수 이 문제에서는 입력은 표준 입력을 사용한다. 입력의 첫 줄에는 T개의 테스트 케이스가 주어진다. 각 테스트 케이스에는 두 개의 정수 k와 n이 주어지며, k( 1 ≤ k ≤ 40,000,000)는 보트의 특정 값 그 www.acmicpc.net 4개의 반을 0반 ~ 3반으로 나누고, vector people01 에는 0반과 1반 학생의 조합으로 나오는 값들을 저장해 놓고, vector people23 에는 2반과 3반 학생의 조합으로 나오는 값들을 저장해 놓은 뒤 중복된 숫자를 제거하여 두 벡터를 이용해 중간에서 만나는 투포인터를 이용해 문제를 해결했다. 이때 중간에서 만다는 투포인터를 두 가지로 나눠서 확인을 했는..

https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 백트래킹으로 문제를 고르는 상황을 확인하여, 해당 상황이 조건에 만족하는지 확인하는 방법을 통해, 조건에 만족해서 문제를 고르는 경우의 수의 개수를 구했다. 코드 #include #include #include using namespace std; int n; vector a; int l, r, x; int result = 0; void Solve(int last_selected, int sum, int high_level, int low_level) { //문제를 고르는 조건을 만족했을때 if (sum >=..

https://www.acmicpc.net/problem/15647 15647번: 로스팅하는 엠마도 바리스타입니다 로스팅하는 엠마는 바리스타입니다. 엠마는 N개의 정점을 가진 트리 형태의 농장 연결 시스템을 구축한 상태입니다. 트리의 정점은 1번부터 N번까지 번호가 매겨져 있습니다. 각각의 간선은 그 www.acmicpc.net 해당 문제의 풀이법은 이전에 작성했던 백준 7812번 : 중앙 트리 (https://geniusjo-story.tistory.com/462) 풀이와 비슷합니다. 농장을 트리로 표현한 뒤, 트리로 만들 때 'subtree_size[정점] = 해당 정점이 루트인 서브트리의 크기'와 'subtree_cost[정점] = 해당 정점이 루트인 서브트리에서 루트에서 각 정점으로 가는 비용의 ..

https://www.acmicpc.net/problem/17469 17469번: 트리의 색깔과 쿼리 N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의 www.acmicpc.net 간선을 제거하는 1번 쿼리가 총 N-1번 있으므로, 들어오는 모든 쿼리를 저장해 놓고 거꾸로 모든 정점이 다 끊어진 상황에서 1번 쿼리시 정점의 간선을 연결하는 오프라인 쿼리를 통해 문제를 해결했다. 1번 쿼리시 정점의 연결은 유니온 파인드의 유니온을 통해 정점의 그룹을 합치면서 그룹이 가지고 있는 색깔도 합쳤고, 2번 쿼리시 유니온 파인드의 파인드를 통해 해당 정점 그룹이 가지고 ..

https://www.acmicpc.net/problem/3090 3090번: 차이를 최소로 각각의 테스트 케이스에 대해서, 점수는 (100×(S+1)/(D+1))/(데이터 개수) 점이다. 이때, D는 출력한 수열에서 인접한 수의 차이의 최댓값, S는 정답이다. 즉, 출력한 수열이 정답인 경우 10점을 얻게 www.acmicpc.net 이분 탐색 (매개 변수 탐색, Parametric Search)을 이용해 인접한 수의 차이가 특정 차이 이하로 만들 수 있는지 확인하는 방법을 통해 문제를 해결했다. 이때, 인접한 수의 차이를 특정 값(check_dist) 이하로 가능한지 판별하는 방법으로, 앞에서부터 뒤쪽으로 확인하며, (check_dist < 뒤쪽값 - 앞쪽값) 인지 확인해서, (check_dist <..