본문 바로가기

알고리즘90

codeforces #581 div2 C - Anna, Svyatoslav and Maps ( 플로이드 ) https://codeforces.com/contest/1204/problem/C 루프가 없는 단방향 그래프에 대해, 임의의 경로를 입력으로 주고, 그 입력의 처음과 끝은 그대로이지만 경로는 똑같을 수 밖에 없는 정점의 배열을 출력하는 문제. (물론 그 배열의 크기는 최소가 되도록.) 위와 같은 그래프와 입력이 1 2 3 4 1 2 3 4 일떄 출력은 1 2 4 2 4 이다. 1 3 4 2 4가 안되는 이유는 3번 정점을 방문하면 입력한 경로에서 벗어나기 때문이다. 풀이) 1. 첫번째 정점과 마지막 정점은 항상 출력해야 한다. 그리고 int arr[]에 입력 경로가 담겨있고, vector ans에 출력할 정답을 담는다고 하자. (pair엔 정점번호, 입력배열에서의 인덱스) 여기서 인덱스를 저장하는 것은 .. 2019. 11. 4.
codeforces #597 div2 D - Shichikuji and Power Grid ( MST ) https://codeforces.com/contest/1245/problem/D 도시(최대 2000)마다 좌표, 파워설치비용, 간선연결가중치가 주어진다. 0번도시를 dummy vertex로 두고, 이 도시랑 연결하는 비용을 파워 설치 비용으로 둔 후, 모든 간선을 정렬하여 mst를 수행한다. mst를 뽑을 때 한 쪽 정점이 0번도시라면 그 도시는 파워를 설치한 도시이고, 양쪽 다 0번이 아니라면 두 도시는 연결된 도시이다. #include #include #include #include using namespace std; typedef pair P; typedef long long ll; const int MAX = 2001; struct Edge { int u, v; ll w; Edge(int u1.. 2019. 11. 4.
codeforces #597 div2 C - Constanze's Machine ( 피보나치 , 구현) https://codeforces.com/contest/1245/problem/C 단어를 입력하면 m은 nn으로, w는 uu로 바꿔서 출력하는 기계가 있다. (출력에 m이나, w가 나올 수 없다. 이경우 0 출력) 예를들어 단어에 nnn이라는 문자배열이 있다면, 가능한 입력은 nnn mn nm 총 세가지가 존재한다. 'n'이 k번 연속한 문자배열을 만들 수 있는 입력은 피보나치 수열을 이루게 된다. (왜 그런지는 모르겠다. 몇번 해보니까 규칙이 보임) 따라서 단어에서 n이 나오는 idx를 기록한 idx_n과 u가 나오는 idx를 기록한 idx_u에 대해서 적절히 연산해 주었다. #include #include #include using namespace std; const int MAX = 1e5+1; .. 2019. 11. 3.
SW 8568 - 3으로 나눈 순열 (발상) https://suuntree.tistory.com/75?category=797985 koi 모양정돈에서 썻던 논리와 같은 논리로 풀 수 있다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW1B8rJq3NUDFARC&categoryId=AW1B8rJq3NUDFARC&categoryType=CODE #include #include using namespace std; int main() { int testcase; cin >> testcase; for (int tc = 1; tc > n; for (int i = 1, input; i > input; if (input % 3 != i % 3) arr[i % 3][.. 2019. 11. 3.

티스토리툴바