1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제는 간단합니다. x,y좌표를 기준으로 상하좌우로 가장 가까운 곳을 찾으면 됩니다. 코드1 #define _CRT_SECURE_NO_WARNINGS #include int main() { int x, y, w, h; int distance; int distance2; scanf("%d %d %d %d", &x, &y, &w, &h); if (w - x < x) distance = w - x; else distance = x; if (h - y < ..

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 서론 이 문제는 자연수의 범위가 (1 ≤ M ≤ N ≤ 1,000,000) 까지 주어졌다. 즉, 최대 백만개가 되는 수들이 소수인지 판단해야 하기 때문에 일반적인 소수 구하는 방식으로는 시간초과가 뜰 것이다. 그래서 사용할 방법이 에라토스테네스의 체이다. 에라토스테네스의 체 간단한 개념이다. 소수는 자기자신과 1로 밖에 나누어지지 않는 수이다. 그러면 어떤 수의 배수는 소수가 될 수 없다. 그래서 2의 배수인 4,6,8 ... 들은 소수가 될 수 없고, 3의 배수도 마찬가지로 6, 9, 12 ..

11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 개념은 조합의 설명을 보면 알 수 있습니다. 조합은 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것인데, 그 경우의 수가 이항계수입니다. 이 이항계수를 나타내는 방법은 $$ _n \mathrm{ C }_k$$ 또는 로 나타낼 수 있습니다. 요약하자면 이항 계수는 조합의 가짓수를 뜻하고, 이항의 의미는 뽑거나, 안 뽑거나 두 가지의 경우만 있기에 이항이라는 단어가 붙었습니다. 이항계수 구하는법 n! / k!(n-k)! 를 그대로 구현하는 방법. 점화식을 사용하기. 저는 구현할 때 점화식을 사용해 재귀로 구현했고,..

2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 최대공약수와 최소공배수 문제를 보았을 때, 내가 알던 식으로 소인수분해를 하며 풀면 안될 것 같다는 생각이 들었다. 그래서 찾아보게 된 것이 유클리드 호제법이다. 유클리드 호제법 유클리드 호제법을 통해 최대공약수를 구할 수 있는데, 이것에 대한 설명은 다음과 같다. 숫자가 a와 b가 있고, a를 b로 나눈 나머지를 r이라고 한다. (여기서 a ≥ b이고, r은 0≤ r < b인 정수) a와 b의 최대 공약수를 (a,b)라고 하면, 다음이 성립한다. (a, b) = (b, r) 예시로 1071과 1029에 대한 예시를 위와 같은 ..