SM's Development Log

문제N(1≤N≤100,000)개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M=3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다. 입력첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다. 출력첫째 줄에 M 이상이면서..

문제크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다. 이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그리고 나서 0행 1열에 숫자 2를 쓴다. 거기서 부터 소용돌이는 반시계 방향으로 시작된다. 다음 숫자는 다음과 같이 채우면 된다. -3 -2 -1 0 1 2 3 ---------------------3 |37 36 35 34 33 32 31-2 |38 17 16 15 14 13 30-1 |39 18 5 4 3 12 29 0 |40 19 6 1 2 11 28 1 |41 20 7 8 9 10 27 2 |42 21 22 23 24 25 26 3 |43 44 45 46 47 48 49이 문제는 위와 같이 채..

문제2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 코드C++ 17#include #include using namespace std; bitset Numbers;int N, K; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.t..

문제에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.이 알고리즘은 다음과 같다.2부터 N까지 모든 정수를 적는다.아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000) 출력첫째 줄에 K번째 지워진 수를 출력한다. 코드C++ 17 #include #include using namespace std; bitset Numbers; int N, K; int ..

문제케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.케빈 베이컨은 미..

문제 방정식 Ax + By + C = 0의 해의 개수를 구하는 프로그램을 작성하시오. A, B, C, x, y는 모두 정수이고, x1 ≤ x ≤ x2, y1 ≤ y ≤ y2인 해의 개수를 구해야 한다. 입력 첫째 줄에 A, B, C, x1, x2, y1, y2가 주어진다. 모든 정수는 -108보다 크거나 같고, 108보다 작거나 같은 정수이다. 출력 첫째 줄에 입력으로 주어진 방정식의 해의 개수를 출력한다. 예제 // 입력 1 1 1 -20 20 -30 30 // 출력 41 // 입력 20 30 40 50 60 70 80 // 출력 0 // 입력 -100 20 300 -100 200 -2000 3000 // 출력 301 // 입력 -10 8 4 -100 100 -200 300 // 출력 50 코드 C++..

문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 bin(N,K)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N) 출력 bin(N,K)를 1,000,000,007로 나눈 나머지를 출력한다. 예제 // 입력 5 2 // 출력 10 코드 C++17 #include using namespace std; using LL = long long; constexpr LL M = 1'000'000'007; LL N, K; LL kFact, invOfkFact, numer; inline LL power(LL x, LL y) { LL toRet = 1; while (y > 0) { if (y & 1) t..

문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 예제 // 입력 4 1 3 5 7 // 출력 3 코드 C++17 #include using namespace std; bool primes[1001] = { true, true }; int N, ans; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // 에라토스테네스의 체 for (int i = 2; i N; for (int i = 0; i < N; ..

문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) 출력 상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정..

문제 최근에 개발된 지능형 기차가 1번역(출발역)부터 4번역(종착역)까지 4개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. 이 장치를 이용하여 출발역에서 종착역까지 가는 도중 기차 안에 사람이 가장 많을 때의 사람 수를 계산하려고 한다. 단, 이 기차를 이용하는 사람들은 질서 의식이 투철하여, 역에서 기차에 탈 때, 내릴 사람이 모두 내린 후에 기차에 탄다고 가정한다. 내린 사람 수 탄 사람 수 1번역(출발역) 0 32 2번역 3 13 3번역 28 25 4번역(종착역) 39 0 예를 들어, 위와 같은 경우를 살펴보자. 이 경우, 기차 안에 사람이 가장 많은 때는 2번역에서 3명의 사람이 기차에서 내리고, 13명의 사람이 기차에 탔을..