더보기 ★★★★★★☆☆☆☆ 문제 접근방식 처음에는 톱니바퀴를 생각했다. 톱니가 10개인 바퀴와 12개인 바퀴로 생각해서 각 바퀴가 돌아갈 때 두 수의 차이만큼씩 간격이 생길 거라고 생각했다. 이게 무슨 말이냐면 아래와 같이 생각했다. 큰 바퀴가 돌 때마다 큰 바퀴의 수를 고정해놓으면 작은 바퀴의 수는 2씩 차이가 난다. 그래서 만약 x, y가 3,9이면 차이가 6이니까 2와 2x의 차이가 6인 줄(위에 표에서 해당)에서 x와 2의 차이만큼 n에 더 해주었을 때 y와 같으면 정답일 거라고 생각했다. ex) m=12, n=10, x=9, y=3일 때 9-3=6, 위의 표에서 세 번째 줄의 6에 7을 더 해주면 3이나 온다. 이런 식의 접근을 했는데 반례가 너무 많았다. 그래서 이 로직을 더 고민하면서 몇 가..

★★★★★★★☆☆☆ 문제 접근 방식 처음에는 팩토리얼로 조합의 개수를 직접 구해 해결하려고 했었다. 조합의 공식이 n!/r!(n-r)! 이므로, n의 최댓값이 너무 크게 주어져 integer overflow가 발생한다. 시간적으로도 불가능하고, 그래서 고민을 오래동안 했는데, 결국 0의 개수라는 게 10이 몇 번 곱해졌냐라는 뜻인데, 곱해서 10이 나오는 수는 2,5이다. 그래서 만약 10! 이면 1*2*3..*10 이런 식에서 각수에 2와 5가 있는지를 찾으면 해결할 수 있을 줄 알았다 하지만, 20억 팩토리얼이면 for문을 20억 번 돌아야 하므로 주어진 시간 내에 절대 해결할 수가 없었다. 그러다가 종이에 팩토리얼을 막 쓰고 (아마 25팩이었던 것 같다) 멍 때리고 있었는데 5의 배수는 결국 5를 ..

★☆☆☆☆☆☆☆☆☆ 문제 접근방식 첫 번 재원이 돌면 나머지가 몇 바퀴를 도느냐를 출력하는 문제이므로 첫 번 재원의 지름만큼 나머지 원이 돈다고 생각했다. 원의 지름 공식은"2πr"인데 r을제 외하 곤 세원이 공통으로 들어가니 지름도 구할 필요 없이 작은 원의 반지름/큰 원의 반지름이 도는 바퀴수가 된다. 기약 분수로 출력하라고 했으니 약분만 해주면 간단한 문제이다. int den, num; //분모 분자 for (int i = 1; i < _r.size(); i++) { num = _r[0]; //첫번째원 den = _r[i]; //else if (num % den == 0) { //분모 분자가 나누어 떨어질때 cout

★★☆☆☆☆☆☆☆☆ 문제 접근 방식 이문제도 숫자 제한이 만까지 걸려있어서 만까지의 숫자를 모두 소수 판독을 한다. n이 입력되면 골드바흐 파티션을 구하기 위해 중간값을 기준으로 작은 값+큰 값이 n과 같을 때 1차 조건 충족, 충족했을 때의 둘의 차이를 저장해놓고 이 값이 최소인지를 비교하는 게 2차 조건. 이렇게 두고 문제 접근을 시작했다. cin >> t; while (t--) { cin >> n; int mid = n / 2; for (int i : decimal) { if (i > mid)break; //비교할 두소수중 작은 소수를 고르기위해 중간값보다커지면 break total += i; //total에 i넣고 for (int j : decimal) { total += j; //total에 j..

★☆☆☆☆☆☆☆☆☆ 문제 접근방식 우선 입력될 숫자의 최댓값이 123456*2이고, 수업 때 배운 에라토스테네스의 체를 이용하여 소수를 미리 선별한다. 그리고, 소수를 저장한 배열에서 (n,2n] 범위에 있는 소수들을 출력하면 되는 문제라고 생각했다. vectorsubdivide(246913, true); //123456*2까지이므로 미리 사이즈설정 decimal.push_back(1); //소수(decimal)배열에 1을 넣고 시작 for (int i = 2; i < subdivide.size(); i++) { //2부터 끝까지 if (subdivide[i]) decimal.push_back(i); //true면 소수 index = i; while (index < subdivide.size()) { /..

내가 느낀 난이도:★★★★☆☆☆☆☆☆ 문제 접근 방법 나는 문제를 읽어보고 큐를 쓰면 좋겠다고는 생각했는데, 방법이 막 떠오르지 않았다. 왜냐하면 입력받는 변수가 많아서 겁에 질렸기 때문이다. 그래도 해야지 뭐, 하여튼 일단 다리를 큐로 생각하고 조건이 무게와 길이인데, 무게는 그냥 total 만들어서 다리 위에 있는 무게의 총량이랑 대기 중인 차량의 무게를 더해서 다리의 최대하중보다 크지 않으면 큐에 추가하고 아니면 대기시켰다. 길이 같은 경우는 큐의 size와 다리의 길이를 비교해 여유 있을 때 차량을 추가해주었다. //트럭리스트에서 조건에 충족하면 큐로 넣음 #include #include #include using namespace std; deque bridge; queuecar..