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..
https://www.acmicpc.net/problem/4153 4153번: 직각삼각형 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. www.acmicpc.net 직각삼각형인지 판단하는 문제. 피타고라스의 정리를 모르는 사람은 없을 것이다. #include int cheaker (int a, int b, int c) { int temp; if (a > c) { temp = a; a = c; c = temp; } else if (b > c) { temp = b; b = c; c = temp; } return a*a + b*b == c*c; } int main () { int ..
https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 입력받은 수들에서 소수의 개수를 출력하는 문제. 저번에 만든 에라토스테네스의 체를 이용하면 된다. #include #include int main () { bool seive[1001] = {false, false}; for (int i = 2; i < 1001; i++) { seive[i] = true; } for (int i = 2; i < 1001; i++) { if (seive[i]) { for (int p = 2; i*p < 1001; p++) { seiv..
https://codejin.tistory.com/31 백준 1929번 C언어 풀이 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.a.. codejin.tistory.com 이 문제를 풀고 난 후에, 에라토스테네스의 체 알고리즘이 더 효율적이라고 조언을 받았다. 그래서 이 알고리즘으로 다시 풀어보았다. 에라토스테네스의 체는 소수를 찾는 하나의 알고리즘인데, 2부터 시작하여, 2의 배수를 모두 지운다. 그리고 1을 더한 3의 배수들도 지운다. 또 1을 더하면 4가 되는데, 아까 2의 배수들이 모두..
https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 주어진 범위 내에서 소수들을 출력하는 문제. 알고리즘 자체는 쉬우나, 소수 판별의 경우 판별해야 하는 수가 매우 커질수록 엄청난 시간이 소요된다. 이를 해결하기 위해 최대한 시간을 줄여보려고 하였다. 사용되는 방법들은 보통 A라는 수를 2부터 A-1까지 나눠보면서 나누어 떨어지는 수가 발견되면 합성수로 판단하면 된다. 하지만 A가 커지면 커질수록 이 판단하는데 소요되는 시간이 길어질 뿐더러, 만약 A가 무진장 큰 소수인 경우, ..
