0과 1의 쉼터

풀이 모든 쌍의 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]

풀이 정답은 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 = ..

풀이 비트 연산자를 사용해 풀이할 수 있다. X의 이진수를 right shift 해주면서, A를 한 번씩 제곱해주다가, X의 이진수의 가장 끝(맨 오른쪽) 숫자가 1일 때, result에 곱해주는 방식으로 풀이했다. A = 2, X = 6일 때 A X X & 1 result 2 110 false 1 4 11 true 4 16 1 true 64 0 소스코드 #include #define MOD 1000000007 int main() { unsigned long long A, X, result = 1; scanf("%llu %llu", &A, &X); A %= MOD; while (X > 0){ if (X & 1) result = (result*A) % MOD; X >>= 1; A = (A*A) % MOD;..

풀이 분할 정복을 이용한 거듭제곱 알고리즘의 기초적인 방법으로 풀이했다. 입력된 수는 int형으로 충분히 담아낼 수 있지만, 두 수의 곱은 이를 벗어나기 때문에, long long형으로 담아주어야 한다. Test Case에 주어지는 C의 값은 결과를 int형으로 출력할 수 있게 주어지는 듯 했다. 착한 문제지 쉬운 문제는 아니다. 홀수의 경우에는 A를 한번 더 곱해서 맞춰주어야 하므로 (B%2 ? A : 1) 으로 해결했다. 소스코드 #include long long mul(int A, int B, int C) { if (B > 1) { long long temp = mul(A, B/2, C); return ((temp*temp)%C * (B%2 ? A : 1)) % C; } else return A; ..

풀이 사분면을 탐색해 방문횟수를 반환하는 방식보다는, 전체 허용 범위내 조건 충족시 출력을 하는 방식으로 풀이했다. 허용 범위가 아니라면, 다른 사분면에 있으므로 n*n을 누적해준다. 소스코드 #include int r, c, cnt; void Z(int row, int col, int n){ if (row == r && col == c){ printf("%d\n", cnt); return; } if (r >= row && c >= col && r < row + n && c < col + n) { Z(row, col, n/2); Z(row, col + n/2, n/2); Z(row + n/2, col, n/2); Z(row + n/2, col + n/2, n/2); } else cnt += n*n; } ..

풀이 약수가 모두 주어지므로 가장 작은 약수와 가장 큰 약수의 곱이 N이다. 소스코드 #include int main(){ int N, val, max, min; scanf("%d", &N); for (int i = 0; i max && (max = val); val < min && (min = val); } printf("%d", max*min); } 출처 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, ..

풀이 256 ~ 0까지 모든 높이의 평지를 만들어보며 최단 시간을 구하는 문제이다. 동일한 층의 개수를 배열로 입력받았고, 가장 높은 층을 구했다. 최단시간이 동일하다면, 높이가 가장 높은 것을 출력해야 하기 때문에 256부터 0으로 내려가면서 탐색했다. (만약 시간이 동일하다면 높은 층의 기록이 유지되므로) 최대 시간(result)은 다음과 같다. 땅의 크기(500 x 500) x 설치(2) x 최대높이(256) = 128,000,000 소스코드 #include int main(){ int N, M, B, arr[257] = {0, }, temp, max = 0; scanf("%d %d %d", &N, &M, &B); for (int i = 0; i < N*M; i++){ scanf("%d", &tem..

풀이 0을 입력받으면 pop, 아니면 push이다. 연산 효율을 위해 일단 입력받고 0이면 top를 -2만큼 감소시켰다. 소스코드 #include int main(){ int K; scanf("%d", &K); int stack[K], top = -1, sum = 0; for (int i = 0; i < K; i++){ scanf("%d", &stack[++top]); if (!stack[top]) top -= 2; } for (int i = 0; i