0과 1의 쉼터

풀이 A는 오름차순, B는 내림차순으로 정렬 후 곱한 값들을 더해주면 된다. 소스코드 #include #include int compare1(const void *a, const void *b){ int n1 = *(int *)a, n2 = *(int *)b; if (n1 n2) return 1; return 0; } int compare2(const void *a, const void *b){ int n1 = *(int *)a, n2 = *(int *)b; if (n1 > n2) return -1; else if (n1 < n2) return 1; return 0; } int main(){ int N; scanf("%d", &N); int A[N]..

풀이 숫자가 아닐 때까지 숫자로 변환해 temp에 저장하다가 부호를 만나면 sum에 저장했다. 처음에 숫자가 입력되므로 양수이기 때문에 '-'일 때, sub[0]에 저장을 해주고 sub[1] 이후로는 빼줄 수를 저장했다. 소스코드 #include #include #include int main() { char str[51]; scanf("%s", str); int len = strlen(str), sub[25] = {0,}, cnt = 0, sum = 0, temp = 0; for (int i = 0; i

풀이 depth가 0일 때는 배열에 첫 수를 넣어주고, 아닐 때는 배열에 없는 수를 찾아서 넣어준다. void BT(int depth){ for (int i = 1; i

풀이 입력받은 컴퓨터 쌍을 서로 접근할 수 있도록 반대 쌍 또한 값을 설정해주었다. 그리고, 이전에 접속한 컴퓨터에서의 탐색(중복)을 막기 위해 컴퓨터 번호에 해당하는 num배열의 값을 증가시켰다. 소스코드 #include int arr[100][100], num[100], N, cnt; void dfs(int worm){ cnt++, num[worm] = 1; for (int i = 0; i < N; i++) if (arr[worm][i] && !num[i]) dfs(i); return; } int main(){ int line, x, y; scanf("%d %d", &N, &line); for (int i = 0; i < line; i++){ scanf("%d %d", &x, &y); arr[x-1]..

풀이 start, end로 배열의 index를 조작하여 합을 구하다가 M 이상일 때는 start가 가르키는 값을 빼고, start를 증가시킨다. M 미만일 때는 end가 가르키는 값을 더하고, end를 증가시킨다. 위 과정을 거친 후 sum이 M과 동일할 때, cnt를 증가시킨다. 소스코드 #include int main(){ int N, M; scanf("%d %d", &N, &M); int arr[N]; for (int i = 0; i < N; i++) scanf("%d", &arr[i]); int start = 0, end = 0, sum = 0, cnt = 0; while (end

풀이 "백준 11659, 구간 합 구하기 4"와 비슷한 문제이다. 단 sum에 저장되는 큰 수의 절대값이 1,000,000,000이므로 int형으로 선언해도 된다. 소스코드 #include int sum[100001]; int main(){ int N, M, first, last, num; scanf("%d", &N); for (int i = 1; i

풀이 편의를 위해 합 또한 2차원 배열로 저장을 해주었다. 다음은 문제의 예제로 주어진 표에 대한 누적 합을 저장한 배열 sum이다. [x, y]가 의미하는 바는 [1, 1] 부터 [x, y]까지의 누적 합이다. 만약, [2, 3](초록색), [4, 4](노랑색) 구간의 합을 구할 때, [2, 3]을 기준으로 불필요한 누적 합인 [1, 4](=10), [4, 2](=24)을 빼주면 된다. 하지만, [1, 4]와 [4, 2]를 빼는 과정에서 공통된 누적 합(분홍색)을 두번 빼므로, [1, 2]를 더해주어야 한다. 정리하면 다음과 같다. // input :: 4 4 2 3 sum[x2][y2]- sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] // ex) [4, 4] -..

풀이 마지막 예제에서 힌트를 얻었다. 입력된 두 정수의 최대공약수 만큼 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로 ..