일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 백트래킹
- 실버
- Class 2
- 실버 V
- Class 3
- 정렬
- 수학
- 구현
- practice
- 골드
- 다이나믹 프로그래밍
- Class 1
- 실버 III
- class 5
- 그래프 이론
- 브론즈 II
- solved.ac class
- Easy
- 브론즈 III
- greedy
- PS
- 브루트포스 알고리즘
- 사칙연산
- 그래프 탐색
- 브론즈
- Class 4
- 문자열
- 너비 우선 탐색
- 한국정보올림피아드
- 정수론
- Today
- Total
목록실버 V (19)
0과 1의 쉼터
풀이 X를 비트로 표현했을 때 1의 개수가 필요한 막대의 개수와 일치한다. 소스코드 #include int main(){ int X, cnt = 0; scanf("%d", &X); do{ if (X & 1) cnt++; } while (X >>= 1); printf("%d", cnt); } 출처 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net
풀이 비트연산자를 이용해 풀이하는 문제이다. all은 반복문을 돌릴필요없이 2^21에서 1을 빼면 20칸의 비트가 모두 1이 된다. 소스코드 #include #include int main(){ int M, S = 0, num; char op[7]; scanf("%d", &M); while (M--){ scanf("%s", op); if (!strcmp(op, "all")) S = (1
풀이 단순히 가장 큰 제곱수로 수를 구성하는 방법은 최소 제곱수의 개수의 만족이 성립하지 않는다. 때문에, 입력받은 n까지 모든 수에 대해 계산을 해봐야 한다. Square Free Integer같은 경우 이전의 수를 구성하는 제곱수의 개수 + 1을 만족하며 이러한 수의 밀집도는 리만 가설이 참이라는 전제하에 약 61%이다. ("백준 1557, 제곱 ㄴㄴ" 중 "Mobius function의 반환값의 개수 추측") 따라서 다음과 규칙을 기본으로 사용했다. for (int i = 1; i = 4 일 때는 Square Free Integer가 아닌 수들도 존재하며, 처음에 언급했듯이 가장 큰 제곱수의 구성이 최소 제곱수의 개수를 만족하지 않으므로, 구성 가능한 제곱수들 중 최소 제곱수의 개수를 찾아야 한다...
소스코드 #include int N; const char *str[7] = { "\"재귀함수가 뭔가요?\"", "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.", "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.", "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"", "\"재귀함수가 뭔가요?\"", "\"재귀함수는 자기 자신을 호출하는 함수라네\"", "라고 답변하였지." }; void message(int n){ for (int i = 0; i < 4; i++){ for (int j = 1; j < n; j++) printf("____"); puts(str[i]); } if (n..
풀이 별을 아래의 그림처럼 노란색, 연두색, 하늘색으로 나누어 찍었다. if (abs(j) >= N-1 && abs(i) == N-1) putchar('*'); // 노란색 else putchar((abs(j)-abs(i) == N-1) || (abs(i)==abs(j)) ? '*' : 32); // 연두색 || 하늘색 마지막 별을 찍고 개행을 해야 한다는 점을 유의하자. 소스코드 #include #include int main(){ int N; scanf("%d", &N); for (int i = -N+1; i = N-1 && abs(i) == N-1) putchar('*'); else ..
풀이 두 수의 곱을 최대공약수로 나누면 최소공배수이다. 소스코드 #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..
풀이 약수가 모두 주어지므로 가장 작은 약수와 가장 큰 약수의 곱이 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보다 크거나 같은 자연수이고, ..
풀이 난이도에 비해 조금 까다로운 문제이다. n을 포함하는 범위(min ~ max)를 알아낸 후, n을 포함하는 범위의 개수를 알아내야 한다. 소스코드 #include #include int compare (const void *a, const void *b){ int n1 = *(int*)a, n2 = *(int*)b; if (n1 n2) return 1; return 0; } int main(){ int L, n; scanf("%d", &L); int S[L]; for(int i = 0; i < L; i++) scanf("%d", &S[i]); scanf("%d", &n); qsort(S, L, sizeof(int), compare); int m..