https://www.acmicpc.net/problem/2611 2611번: 자동차경주 첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어 www.acmicpc.net 1번 정점에서 출발해서 1번 정점으로 다시 돌아올 때까지 위상 정렬을 해 나아가면서 cache에 해당 지점에서 최대 점수를 저장해 나아가는 방법을 통해 문제를 해결했다. #include #include #include #include using namespace std; int n; int m; vector adj[1001]; vector indegree(1001, 0); queue q;..

https://www.acmicpc.net/problem/15586 15586번: MooTube (Gold) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 질문을 다 저장하고, 질문에서 k의 내림차순으로 정렬하고, 정렬한 순서대로 다시 질문하는 오프라인 쿼리를 이용했다. 해당 질문의 k이상으로 이루어진 간선들만 연결시켜가며 그래프를 만들고 유니온 파인드를 통해 해당 정점의 그룹을 확인하는 과정을 통해 문제를 해결했다. 코드 #include #include #include #include using na..

https://www.acmicpc.net/problem/1994 1994번: 등차수열 N개의 음 아닌 정수들이 있다. 이들 중 몇 개의 정수를 선택하여 나열하면 등차수열을 만들 수 있다. 예를 들어 4, 3, 1, 5, 7이 있을 때 1, 3, 5, 7을 선택하여 나열하면 등차수열이 된다. 이와 같이 www.acmicpc.net 중복되는 수의 개수를 세어서 등차가 0일 때 등차수열의 길이를 구하고, 중복되지 않게 수를 저장한 뒤 index1번째 숫자와 index2번째 숫자로 시작하는 등차수열의 길이를 다이나믹 프로그래밍을 이용해 문제를 해결했다. index1번째 숫자와 index2번째 숫자 뒤에 나오는 숫자를 찾을 때는 이분 탐색을 이용하여 문제를 해결했다. 코드 #include #include #in..

https://www.acmicpc.net/problem/22988 22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 중간에서 만나는 투 포인터를 사용해서 두 개의 용기로 용량을 꽉 차게 만들 수 있는지 확인하여, 만들 수 있으면 해당 두 개를 선택하여 꽉 찬 용기를 만든다. 선택되지 않는 남은 용기가 3개 이상이면 두 개를 합치면 무조건 x/2 이상이 되고, 이것을 나머지 한 개와 합치면 x이상을 만들 수 있으므로 3개를..

https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 각 칸에서 몇 점을 얻을 수 있는지 계산을 해 놓고, 주사위를 움직이는 방법으로 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n, m, k; int board[20][20]; int result = 0; pair point = make_pair(0, 0); int dir = 2; int dxd..

https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 유니온 파인드로 그룹을 만들고 int cache[3005][2]에 [뺏을 수 있는 인원수][0:이전의 결과, 1:새로운 결과] = 최대 사탕을 저장하여 그룹마다 확인하면서 계속 업데이트해 나아가면 cache[k - 1][0]에 결과값이 저장이 된다. 코드 #include #include #include using..