C

이 문제는 딱봐도 DFS느낌이 바로 왔다. 맵에서 1을 만나는 경우 DFS를 이용해서 개수를 찾으면 될 것 같은 느낌이 왔다. 이 아이디어만 있으면 구현부분에서 잘하면 쉽게 풀 수 있는 문제이다. // 딱봐도 DFS #include #include #include #include using namespace std; vector arr; vector collect; vector dx = {1,0,-1,0}; vector dy = {0,1,0,-1}; int howMany = 0; int N; vector split(string &str){ vector line; for (char c : str){ line.push_back(stoi(string(1, c))); } return line; } void df..

#include #include using namespace std; int main(int argc, char** argv) { int N; int workTimeA, workTimeB, moveTimeAtoB, moveTimeBtoA; vector work, move; cin >> N; for (int i = 0; i > workTimeA >> workTimeB >> moveTimeAtoB >> moveTimeBtoA; work.push_back(make_pair(workTimeA, workTimeB)); move.push_back(make_pair(moveTimeAtoB, moveTimeBtoA)); } int A = 0; // A의 최소 시간 기록 int B = 0; ..

문제를 풀기 전에 분할 정복에 대해서 알아보자. 분할 정복이란, 문제를 풀 때, 비슷한 부분의 작은 부분으로 쪼개서 계산하고 그 결과들을 통해서 답을 도출하는 방법이다. 총 3가지 단계로 나눠서 문제를 풀게 되는데, 1. Divide : 기존 문제를 작은 부분 문제들로 나눈다. 2. Conquer : 각 부분 문제들을 해결 3. Combine : 부분 문제들의 솔루션을 통해서 기존 문제를 해결 이런 식으로 문제를 푼다. 분할정복의 대표적인 예로는 병합 정렬이 있다. 수퍼 바이러스 문제는 계산하면서 수가 너무 커지기 때문에 미리 계산을 해서 그나마 작은 수들로 계산을 해나가야 하기 때문에 분할 정복을 사용해야한다. 여기서 1000000007의 정체를 궁금해 하는 사람이 있을 것이다. 1000000007는 ..