Doby's Lab

https://www.acmicpc.net/problem/14490 14490번: 백대열 n과 m이 :을 사이에 두고 주어진다. (1 ≤ n, m ≤ 100,000,000) www.acmicpc.net 1) 문자열로 입력받아서 while문을 통해 정수로 바꿔주기 2) stoi()를 이용해 문자열 -> 숫자 3) 유클리드 호제법을 이용하여 최대공약수 구하기 4) 두 수에 나눠준 몫을 출력 #include #include using namespace std; int gcd(int a, int b) { if (a % b == 0) { return b; } return gcd(b, a % b); } int main() { string value; cin >> value; string a, b; int cnt =..

이 문제는 크게 고민할 필요 없이 백트래킹으로 쌍 구하고, 최대공약수를 구해 더해나가면 되는 문제였다. 하지만 이를 구현했을 때, 시간 초과가 발생한다. 코드 (시간 초과) 백트래킹에서 발생하는 것인지, 최대공약수를 구하는 함수에서 발생하는 것인지 알 수 없었다. 하지만, 1,000,000을 넘지 않는 수라면 그에 근접하는 엄청 큰 수들이 100개까지 있다고 생각해보면 몇 쌍들이 생길지 모를뿐더러 거기다가 곱하기 1,000,000을 해준다면 엄청 큰 값이 나와서 시간 초과를 유발하는 것을 알 수 있었다. >> 최대공약수를 구하는 함수가 문제다. #include #include #include using namespace std; bool visited[101] = { 0, }; vector two; //..