728x90 🥇Baekjoon Solutions/정수론12 [C++] 백준 1644번: 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 최초풀이 1-4,000,000까지 소수 확보 연속된 소수들의 합을 배열 인덱스로 확인하며 누적 #include #include using namespace std; int check[4000001]; bool Not_prime[4000001]; int main() { int N; vectorprime; //소수가 아닌수 체크(에라토스테네스의 체) for (int i = 2; i N; cout 2021. 7. 31. [C++] 백준 2725번: 보이는 점의 개수 https://www.acmicpc.net/problem/2725 최초풀이 시간초과 에러가 처음 발생하였습니다. 그래서 미리 모든 수를 구해 놓고 결과 값을 구하는 방식을 사용하였습니다. #include #include using namespace std; int gcd(int a, int b) {// 최대공약수 구하기(재귀, 유클리드 호제법) if (b == 0) return a; else return gcd(b, a % b); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int C; vectorv; cin >> C; v.push_back(0); int ans = 0; for (int i = 1; i > N; cout 2021. 7. 31. [C++] 백준 11653번: 소인수분해 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 최초풀이 for문을 활용하여 인수를 찾아줍니다. #include #include using namespace std; // 다른 공약수문제에서 많이 사용되는 기초문제 int main() { int N; vectorv; cin >> N; for (int i = 2; i 2021. 7. 31. [C++] 백준 2824번: 최대공약수 https://www.acmicpc.net/problem/2824 2824번: 최대공약수 첫째 줄에 N이 주어진다.(1 ≤ N ≤ 1000) 둘째 줄에는 N개의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M이 주어진다.(1 ≤ M ≤ 1 www.acmicpc.net 최초풀이 시간초과 에러 시간복잡도가 상당히 발생하는 것 같습니다..ㅠㅠ #include #include #include using namespace std; int A_arr[31624],B_arr[31624]; int gcd(int a, int b) {// 최대공약수 구하기(재귀, 유클리드 호제법) if (b == 0) return a; else retur.. 2021. 7. 30. [C++] 백준 14476번: 최대공약수 하나 빼기 https://www.acmicpc.net/problem/14476 14476번: 최대공약수 하나 빼기 첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다. www.acmicpc.net 최초풀이 #include #include int arr[44722]; using namespace std; // 1-2,000,000,000->44,722 int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, k; vectorv, ans; cin >> N; for (int i = 0; i > k; v.push.. 2021. 7. 30. [C++] 백준 1735번: 분수 합 https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 최초풀이 각각의 분모, 분자 수를 만들어서 각각을 2부터 더작은 수까지 나눌 수 있는 수들을 나누는 방식으로 두수 모두 더이상 나눠지지 않을 때까지 과정을 반복해준다. 주의사항 for을 통해 나눠진다면 나눠질 때마다 i를 1로 초기화해주어야 한다.(중복되는 인수들을 나눠주기 위함) #include using namespace std; int main() { int A1, B1, A2, B2, A, B; cin >> A1 >> B1; cin >> A2.. 2021. 7. 29. [C++] 백준 6588번: 골드바흐의 추측 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 최초풀이 처음 prime 배열을 활용하여 2-1,000,000까지의 모든 소수를 구합니다.(에라토스테네스의 체) 또한 별도의 벡터를 활용하여 소수들만 따로 뽑아줍니다. 추가적으로 시간초가 에러에 대해서는 아래의 코드와 ios_base::sync_with_stdio(false); cin.tie(nullptr); endl 대신 "\n"을 활용하여 처리하여 해결하였습니다. #in.. 2021. 7. 29. [C++] 백준 10430번: 나머지 https://www.acmicpc.net/problem/10430 10430번: 나머지 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) www.acmicpc.net 최초풀이 뒤에 어려운 활용문제가 많이 등장합니다. #include using namespace std; int main() { int A = 0; int B = 0; int C = 0; cin >> A >> B >> C; cout 2021. 7. 28. [C++] 백준 4375번: 1 https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 최초 오류 무작정 11...11인 수를 n으로 나누려한다면 런타임 에러가 발생한다. 이유: 계속 안나눠 진다면 11...11의 길이가 무한정 커져서 계산 자체에 오류가 발생한다. 길이(자리수)가 2000이라면 계산이 될 수 없기 때문이다. 풀이 문제에서 어떤 수로 나누어진다는 것을 판별 할때는 커지는 수를 계속해서 나누려는 수로 나눈나머지로 한정시켜킨다. (a+b)%c = (a%c+b%c)%c (나머지는 같음을 이용함 계속해서 나머지만을 이용) 작은 자리숫.. 2021. 7. 27. 이전 1 2 다음 728x90
