0과 1의 쉼터

소스코드 #include int main(){ int N, M, K, x1, y1, x2, y2; scanf("%d %d", &N, &M); int arr[N][M]; for (int i = 0; i < N*M; i++) scanf("%d", &arr[i/M][i%M]); scanf("%d", &K); while (K--){ scanf("%d %d %d %d", &x1, &y1, &x2, &y2); int sum = 0; for (int i = x1; i

풀이 마지막 예제에서 힌트를 얻었다. 입력된 두 정수의 최대공약수 만큼 1을 출력해주면 된다. 소스코드 #include #define LL long long LL GCD(LL a, LL b){ return b ? GCD(b, a%b) : a; } int main(){ LL A, B; scanf("%lld %lld", &A, &B); LL i = GCD(A, B); while (i--) putchar('1'); } 출처 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net

풀이 입력받은 두 분수를 통분하고, 분자와 분모의 최대공약수를 이용해 약분하여 분수형태로 출력하면 된다. 소스코드 #include int GCD(int a, int b){ return b ? GCD(b, a%b) : a; } int main(){ int A, B, a, b; scanf("%d %d %d %d", &A, &B, &a, &b); int AA = A*b + a*B, BB = B*b; int gcd = GCD(AA, BB); printf("%d %d\n", AA/gcd, BB/gcd); } 출처 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net

풀이 처음에 입력받은 링의 반지름과 이후에 입력받은 반지름의 최대공약수를 이용해 약분하여 분수형태로 출력하면 된다. 소스코드 #include int GCD(int a, int b){ return b ? GCD(b, a%b) : a; } int main(){ int N, first_r, r; scanf("%d %d", &N, &first_r); while (-1 + N--){ scanf("%d", &r); int gcd = GCD(first_r, r); printf("%d/%d\n", first_r/gcd, r/gcd); } } 출처 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 ..

풀이 모든 쌍의 GCD를 구해서 합해주면 된다. 단, 최악의 경우 1,000,000 * 99 * 98 * 97 *... * 3 * 2 *1 의 수가 나올 수 있으니 long long 자료형의 변수에 합을 담아주어야 한다. 소스코드 #include int GCD(int a, int b){ return b ? GCD(b, a%b) : a; } int main(){ int t, n, arr[100]; scanf("%d", &t); while (t--){ scanf("%d", &n); long long gcd_sum = 0; for (int i = 0; i < n; i++) scanf("%d", &arr[i]); for (int i = 0; i < n-1; i++) for (int j = 1 + i; j < n..

풀이 두 수의 곱을 최대공약수로 나누면 최소공배수이다. 소스코드 #include int GCD(int a, int b){ return b ? GCD(b, a%b) : a; } int main(){ int T, A, B; scanf("%d", &T); while (T--){ scanf("%d %d", &A, &B); printf("%d\n", A*B / GCD(A, B)); } } 출처 및 참고자료 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net [백준 2609] 최대공약수와 최소공배수 [C..

풀이 구조체 배열의 index와 문자열을 이용해 숫자를 입력받을 떄는 별도의 탐색없이 출력이 가능하지만, 문자열 검색시에는 탐색을 필요로 하고, 이 과정에서 시간 초과가 발생해 map을 사용해 풀이했다. 소스코드 #include #include #include #include using namespace std; map name; map num; int main(){ int N, M; scanf("%d %d", &N, &M); char temp[21]; for (int i = 0; i < N; i++){ scanf("%s", temp); name[temp] = i; num[i] = temp; } for (int i = 0; i < M; i++){ scanf("%s", temp); if (temp[0]

풀이 Pisano Period를 이용해 풀이했다. 위의 내용 처럼 피보나치 수를 특정 수(n)으로 나눌 때 나머지들은 일정 주기마다 반복되는 것을 알 수 있다. 이러한 주기를 Pisano Period라고 부른다. Pisano Period는 다음과 같이 이용된다. n번째 피보나치 수를 MOD로 나눈 나머지는, N % (Pisano Period) 번째 피보나치 수를 MOD로 나눈 나머지와 같다. Pisano Period번 째의 피보나치 수가 필요하며, 이번 문제에 필요한 Pisano Period를 구하는 방법은 다음과 같다. MOD가 10의 6승이므로 Pisano Period는 1500000 = 15 * 10 ^(5) 이다. 소스코드 #include #define MOD 1000000 #define P 15..

풀이 정답은 2의 K제곱들의 합이다. "백준 13731, A" 문제에서 2의 제곱을 구하는 방식을 이용해 풀이했다. 2의 K제곱(D)들의 합(sum_D)을 차수와 계수의 곱에 곱해주는 것을 반복하면 된다. 소스코드 #include #define MOD 1000000007 int main() { int N; scanf("%d", &N); long long result = 0, C, K; for (int i = 0; i < N; i++) { scanf("%d %d", &C, &K); long long DC = (C*K)%MOD, sum_D = 1, D = 2; K--; while (K) { if (K & 1) sum_D = sum_D*D %MOD; D = D*D %MOD; K /= 2; } result = ..

소스코드 #include int main(){ int N, n1, n2, result = 0; scanf("%d", &N); for (int i = 0; i < N; i++){ scanf("%d %d", &n1, &n2); result += n1*n2; } printf("%d", result); } 출처 14730번: 謎紛芥索紀 (Small) 성민이는 이번 학기에 미적분학 과목을 수강하고 있다. 다항함수의 미분 단원 과제를 하던 도중 미분을 하기가 귀찮아진 성민이는 미분하려는 함수 f(x)가 주어지면, 미분 된 함수 f’(x)를 자동 www.acmicpc.net