https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 규칙성을 찾는데 조금 애먹었다. 군수열에 관한 문제였다. 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → …순서인데 우상단→좌하단방향으로 잘라보면(위의 표에서) 1/1 // 1/2, 2/1 // 3/1, 2/2, 1/3 // 1/4, 2/3, 3/2, 4/1 // ...의 수열을 얻을 수 있다. //를 기준으로 1/1부터 1군이라고 하자. n군..
참 오랜만에 백준을 푼 것 같다. https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 베르트랑 공준에 관한 문제. 임의의 자연수 n에 대해 n ~ 2n사이에 소수는 적어도 하나가 존재한다는 이론이다. 현재 완전히 증명되어있는 이론. 소수문제를 풀면서 에라토스테네스의 체를 한번 구현해 놓으니 거의 모든 소수문제가 복붙수준으로 풀리고 있다. 이 문제도 에라토스테네스의 체를 한번 만들어 놓은 후에, 범위에 따라 개수를 세면 되는 문제. #incl..
https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 조건에 맞게 사람수를 세는 문제. h(0
https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 해시함수에 관한 문제, small과 large문제 합하여 모두 맞춰야 하는 문제인데 자꾸 부분정답만 나온다.... #include #define r 31 #define M 1234567891 long long pown (int a, int exp) { long long res = 1; for (int i = 0; i < exp; i++) { res *= a; } return res; } int ..
https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 조합을 구하는 문제. 이항계수가 뭔지 까먹은 나 자신 반성하자... #include int fac (int n) { int res = 1; while (n > 1) { res *= n--; } return res; } int combination (int n, int r) { return fac(n) / (fac(r) * fac(n-r)); } int main () { int n, r; scanf("%d %d", &n, &r); printf("%d", combination..
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net M개의 수가 N개의 숫자 배열에 들어있는지 찾는 문제. 중첩반복문을 쓸 때 느낌이 쎄하긴 했는데, 시간초과로 틀렸다. 근데 다른 방법이 있긴 한건가? #include int main () { int n, m; int i; int check; scanf("%d", &n); int a[n]; for (i = 0; i < n; i++) { scanf("%..
https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 규칙을 파악하면 금방 풀리는 문제. 함정들에 조심하자. 높이 H에 너비 W, N번째 손님이 주어지는데, 사실 W의 값은 중요하지 않더라. 만약 6 12 10의 입력이 들어오면, 10번째 손님은 402호실에 들어가면 된다. 따라서 층수는 N과 H의 나머지, 호실은 N과 H의 몫 + 1인 셈이다. 이렇게만 보면 쉬운문제이지만, 함정이 있다. N과 H가 나누어 떨어지는 경우 나머지값이 0이..
https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net https://codejin.tistory.com/10 백준 4673번 C언어 풀이 https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어.. codejin.tist..
