EVO

이 문제는 DFS 알고리즘을 사용하여 사이클을 이루지 않는 사람의 수를 구하는 문제 입니다. 내 풀이 방향그래프에서의 사이클이 존재하는 지의 여부는 간선 구분을 통해 판정할 수 있습니다. 사이클이 존재한다는 것은 역방향 간선의 여부와 동치인데 그전에 역방향간선에 대해 간단하게 살펴보자면 그래프에서 Ti부터 DFS알고리즘을 돌리면 트리형태를 띠게됩니다. 그러한 트리를 DFS 스패닝 트리라고 합니다. (Tm, Tj)의 간선은 스패닝트리의 자손에서 선조로 연결된 간선인 역방향 간선입니다. 그래서 사이클이 있는 그래프를 깊이우선탐색을 할 경우 무슨일이 벌어질지 생각해보면 쉽게 이해를 할 수 있습니다. 사이클에 포함된 정점 중 깊이 우선 탐색과정에서 처음만나는 정점을 u(Tj)라고 합시다. dfs(u)는 u에서 ..

https://www.acmicpc.net/problem/15486 남은 N일 동안 최대한 많은 상담을 하려고 한다. 쉽게 생각해보면 day[상담을 잡은 날] = ? //?: ex=3 상담을 잡은 날 + day[상담을 잡은 날] =>ex) 1+array[1] = 1+3 = 4 // 4일째부터 가능 result+=profit[상담을 잡은 날] 일단 가장먼저 생각나는 dfs를 이용한 완전탐색으로 풀어보면 #include #include #include using namespace std; int N; int day[1500001]; int profit[1500001]; int maxRes = -10000; void dfs(int 상담날짜,int 총금액) { int 금액 = profit[상담날짜]; 총금액 +..

처음 아기상어 크기: 2 1초에 상하좌우로 인접한 한 칸씩 이동 아기상어의 크기 물고기의 크기 : 이동가능O 먹을 수 O 아기상어의 크기 = 물고기의 크기: 이동가능 O 먹을수 X 물고기 먹는 순서 1. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.(9는 상어) 0 0 0 0 0 0 1 0 9 2. 먹을 수 있는 물고기가 1마리보다 많다면 거리가 가장 가까운 물고기를 먹으러간다. 0 1 0 0 0 0 1 0 9 3. 거리가 같은 물고기가 많다면 가장위, 가장 왼쪽 물고기를 먹는다. 1 0 1 0 9 0 0 0 1 먹을 수 있는 물고기가 있는 칸으로 이동했다면 그 칸은 0이 된다. 아기상어는 자신의 크기와 같은 수의 물고기를 ..

한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있고 다솜이의 방 번호가 주어지면 필요한 세트의 개수의 최솟값을 구해야한다. 그래서 예를들면 1234 번호가 주어지면 1,2,3,4번 카드가 각각 1장 씩 필요하므로 이렇게 표현이 가능하다. 이것은 1세트로 가능한 번호이다. 다음 예시로는 1233이 주어졌을때를 보면 1,2는 각각 1장 필요하고 3은 2장이 필요하다 이것은 2세트가 있어야 이 방번호를 표현할수있다. 이렇게 위 배열을 표현하기 위해서는 방번호가 주어졌을때 방번호의 숫자를 분리하고 그 숫자에 해당하는 인덱스값을 1씩 증가 시키면 저 배열이 표현이 가능하다. 그다음으로 배열에 있는 값중 가장 큰 값이 우리가 구하려는 세트의 최솟값이다. 다음으로 고려해야할것은 6과 9이다. 예를들어 669가 주어..

1x1 4개를 이어 붙인다. 총 5가지가 있다. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다. 따라서 5가지가 아니라 파랑색은 2가지 노란색 1가지 오랜지색은 8가지 연두색은 4가지 보라색은 4가지이다. 총 그래서 19가지 이 경우를 모두 할 수 있도록 미리 방향배열을 만들고나서 이 방향배열들을 모두 실행하도록하면 19*4 = 76 그리고 이 76번의 연산이 모든 배열에서 실행되므로 500\*500\*76 = 약 40000 500 => 20000000 약 2천만번의 연산이 일어난다. 시간제한은 2초 약 2억번의 연산을 감당할 수 있으므로 충분히 가능하다. 그래서 브루드포스로 무식하게 풀어도 가능한 문제이다. 그렇게 풀도록 하자. (딱히 다른 ..

문제 분석 예를 들어 2 2 2 4 4 4 8 8 8 이 주어지고 왼쪽으로 이동할때는 4 2 0 8 4 0 16 8 0 의 결과가 나와야 하는데 이러한 결과에 착안해서 해당입력에서 왼쪽으로 이동할때는 왼쪽부터 계산해야한다는 순서가 필요합니다. 좀더 도식화를 시키고 보면 a b c d e f h i j 왼쪽으로 이동할때 보는 순서는 (0,0)⇒(0,1): a와 b가 같을때 (0,0) = a+b (0,1) = 0 a와 b가 다를때 (0,0) = a (0,1) = b 그러나 만약 a가 0이라면 (0,0) = b (0,1) = 0 그 다음은 (0,1)⇒(0,2): b와 c가 같을때 (0,1) = b+c (0,2) = 0 b와 c가 다를때 (0,1) = b (0,2) = c 그러나 만약 b가 0이라면 (0,1) ..

문제 파악 사무실은 NxM 그리고 그 사무실은 총 k개의 cctv설치 cctv는 총 5종류 1번은 한쪽 방향만 감시할 수 있다. 2번은 두방향 감시 단, 직선형태로 감시 3번은 두방향 감시 단, 직각 형태로 감시 4번은 세방향 5번은 네방향 cctv는 벽을 통과 못함 cctv는 통과 할 수 있음 cctv는 회전가능 단 90도방향으로 즉 방향이 가로또는 세로 방향 0번은 빈칸, 6번은 벽, 1~5는 cctv번호 출력=> cctv방향을 적절히 정해서 사각지대의 최소 크기를 구해야한다. 입력=> 1cnt가 2일때 카메라 개수 2와 일치하므로 이때는 완성했으므로 0의 개수를 센다 if (cnt == cctv.size()) { for (int i = 0; i < cctv.size(); i++) { //모든 카메라..

1단계: 문제 이해 2 //테스트 케이스 2번 4 4 // 건물의 개수 4개 , 건설순서의 규칙 개수 4개 10 1 100 10 //1번건물 :10 2번건물:1 3번건물:100 4번건물:10 1 2 // 1번건물 지은다음 2번건물 지을 수 있음 1 3 // 1번건물 지은다음 3번건물 지을 수 있음 2 4 // 2번건물 지은다음 4번건물 3 4 // 3번건물 지은다음 4번건물 4 // 승리하기 위해 4번건물을 지어야 함, 건물 4를 완료하는데 드는 최소 시간을 출력 8 8 10 20 1 5 8 7 1 43 1 2 //1번=>2번 1 3 //1번=>3번 2 4 //2번=>4번 2 5 //2번=>5번 3 6 //3번=>6번 5 7 //5번=>7번 6 7 //6번=>7번 7 8 //7번=>8번 7 //7번이 짓..