수퍼바이러스

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