whitespace

문제

두 학생 A와 B가 일직선상의 트랙에서 같은 방향으로 멀리뛰기를 하고 있다. A는 한 번에 X 미터를, B는 한 번에 Y 미터를 뛴다. 두 학생의 시작 지점과 X, Y에 대한 정보가 주어졌을 때, 두 학생이 공통적으로 지나게 되는 지점 중에서 시작 지점으로부터 가장 가까운 지점을 찾는 프로그램을 작성하시오.

예를 들어 한 번에 10미터를 뛰는 A는 30의 지점에서 멀리뛰기를 시작하고, 한 번에 12미터를 뛰는 B는 8의 지점에서 시작한다고 가정하자. A가 5번의 멀리뛰기를 하고, B가 6번의 멀리뛰기를 하면 두 사람은 80의 지점을 공통으로 지나게 되며, 이는 두 학생의 시작 지점에서 가장 가까운 지점이다.

입력

첫째 줄에 두 사람이 한 번에 멀리뛰기를 하는 거리 X, Y와 시작 지점의 위치 값 P1, P2가 각각 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ X, Y, P1, P2 ≤ 100)

출력

첫째 줄에 두 학생이 공통적으로 지나는 지점 중에서 가장 가까운 지점을 출력한다.

단, 두 학생이 공통적으로 지나는 지점이 없다면 -1을 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

#include<stdio.h>
#include<stdbool.h>

int main(void)
{
	int X, Y, P1, P2;
	bool solved=false;

	scanf("%d %d %d %d", &X, &Y, &P1, &P2);

	for(int i=0;i<=100;i++)
	{
		int K=i*X+P1;
		for(int j=0;j<=100;j++)
			if(K==(j*Y+P2))
			{
				solved=true;
				printf("%d\n", K);
				break;
			}
		if(solved)
			break;
	}

	if(!solved)
		printf("-1\n");

	return 0;
}

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

예제 입력 4

예제 출력 4

#include<stdio.h>
#include<stdbool.h>

bool isPrime(int N)
{
	if(N<2)
		return false;
	else if(N==2)
		return true;
	else if(N%2==0)
		return false;
	else
		for(int i=3;i*i<=N;i+=2)
			if(N%i==0)
				return false;
	return true;
}

int main(void)
{
	int prime_count=1, prime[283146]={2, }, N, count=0;

	scanf("%d", &N);

	for(int i=3;i<=N;i+=2)
		if(isPrime(i))
			prime[prime_count++]=i;

	for(int i=0;i<prime_count;i++)
	{
		int sum=0;

		for(int j=0;sum<N;j++)
			sum+=prime[i+j];

		count+=sum==N;
	}

	printf("%d\n", count);

	return 0;
}

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

예제 입력 1

예제 출력 1

#include<stdio.h>
#include<stdbool.h>

int main(void)
{
	int n;
	bool is_prime[1000001]={false, false, true, };

	for(int i=2;i<1000001;i++)
		is_prime[i]=true;
	for(int i=2;i<1000001;i++)
		if(is_prime[i])
			for(int j=2*i;j<1000001;j+=i)
				is_prime[j]=false;

	scanf("%d", &n);

	while(n>0)
	{
		bool found=false;

		for(int i=3;i<=n/2;i+=2)
			if(is_prime[i] && is_prime[n-i])
			{
				printf("%d = %d + %d\n", n, i, n-i);
				found=true;
				break;
			}

		if(!found)
			printf("Goldbach's conjecture is wrong.\n");

		scanf("%d", &n);
	}

	return 0;
}

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

 입력 1

예제 출력 1

#include<stdio.h>

int main(void)
{
	long long int fibonacci[41][2];
	int T;

	for(int i=0;i<41;i++)
		fibonacci[i][0]=fibonacci[i][1]=0;

	fibonacci[2][0]=fibonacci[2][1]=fibonacci[0][0]=fibonacci[1][1]=1;

	for(int i=3;i<41;i++)
		for(int j=0;j<2;j++)
			fibonacci[i][j]=fibonacci[i-1][j]+fibonacci[i-2][j];

	scanf("%d", &T);

	for(int t=0;t<T;t++)
	{
		int N;

		scanf("%d", &N);

		printf("%lld %lld\n", fibonacci[N][0], fibonacci[N][1]);
	}

	return 0;
}

문제

“반갑다. 내 이름은 반고흐#31555! 조선 최고의 활잡이지. 오늘도 난 금강산 위에서 적들을 노리고 있지. 내 앞에 있는 적들이라면 누구도 놓치지 않아! 좋아, 이제 곧 월식이 시작되는군. 월식이 시작되면 용이 적들을 집어삼킬 것이다. 잘 봐두어라! 마장동 활잡이 반고흐#31555님의 실력을-!”

반고흐#31555는 자기 뒤쪽 봉우리에 덩기#3958이 있음을 전혀 모르고 있었다. 덩기#3958도 반고흐#31555와 마찬가지로 월식이 시작되면 용을 불러내어 눈앞에 있는 다른 활잡이들을 모두 처치할 생각이다. 사실, 반고흐#31555와 덩기#3958 뿐만 아니라 금강 산맥의 N개 봉우리에 있는 모든 활잡이들이 같은 생각을 가지고 있다.

반고흐#31555가 있는 금강 산맥에는 총 N개의 봉우리가 있고, 모든 봉우리마다 한 명의 활잡이가 서서 월식이 시작되기만을 기다리고 있다. 다만, 애석하게도, 천계에 맥도날드가 생겨 용들이 살이 찐 탓에 용들은 자신보다 낮은 봉우리에 서있는 적들만 처치할 수 있게 되었다. 또한 용들은 처음 출발한 봉우리보다 높은 봉우리를 만나면 그대로 공격을 포기하고 금강산자락에 드러누워 낮잠을 청한다고 한다. 봉우리의 높이는 모두 다르고 모든 용들은 오른쪽으로만 나아가며, 중간에 방향을 틀거나, 봉우리가 무너지거나 솟아나는 경우는 없다.

“달에 마구니가 끼었구나.”

드디어 월식이 시작됐다! 과연 이들 활잡이 중 최고의 활잡이는 누구일까? 최고의 활잡이가 최대 몇 명의 적을 처치할 수 있는지 알아보자.

입력

첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이 유일하다.

출력

최고의 활잡이가 처치할 수 있는 적의 최대 숫자를 출력한다.

예제 입력 1

예제 출력 1

힌트

높이 10 봉우리에 있는 활잡이가 높이 2, 5, 7 봉우리에 있는 활잡이들을 처치할 수 있다.

#include<stdio.h>
#include<stdlib.h>

int main(void)
{
	int N, *peak=NULL, max=0;

	scanf("%d", &N);
	peak=(int *)malloc(N*sizeof(int));

	for(int i=0;i<N;i++)
		scanf("%d", &peak[i]);

	for(int i=0;i<N;i++)
		for(int j=i+1;peak[i]>peak[j] && j<N;j++)
			max=j-i>max?j-i:max;

	printf("%d\n", max);

	free(peak);
	return 0;
}

문제

JOI는 친구 1부터 친구 N까지 총 N 명의 친구와 함께, 크리스마스 파티에 갔습니다. 크리스마스 파티 분위기도 달아오르니, JOI는 친구들과 함께 다음과 같은 게임을 하기로 했습니다.

1. 가장 먼저, JOI는 N명의 친구 중 한 명을 선택합니다. 이제 그 친구를 '타겟'이라고 부릅시다.
2. JOI는 타겟으로 고른 친구에게, 타겟이 되었다는 것을 몰래 알려줍니다. 타겟이 아닌 친구들은 누가 타겟인지 알 수 없습니다.
3. 타겟이 아닌 친구들은 각자 타겟이 누구일까 생각해서, 그 사람의 이름을 종이에 씁니다. 타겟은 자기자신의 이름을 종이에 씁니다.
4. 모든 사람이 종이에 이름을 썼다면, JOI는 타겟의 이름을 발표합니다.
5. 예상이 맞은 사람은 1점을 얻습니다. 당연히, 타겟은 자신의 이름을 적었으므로, 반드시 1점을 얻습니다. 예상이 빗나간 사람은 점수를 주지 않습니다.
6. 추가로, 예상이 빗나간 사람의 수가 X명일 경우, 타겟은 추가로 X점을 얻습니다.

 JOI와 친구들은 이 게임을 M번 했습니다. M번의 게임을 했을 때, 각 친구들의 합계 점수를 구하세요.

입력

입력은 총 3 + M 줄이 주어집니다.

첫 번째 줄에는 친구들의 수 N (3 ≦ N ≦ 100)이 주어집니다.

두 번째 줄에는 JOI와 친구들이 했던 게임의 횟수 M (3 ≦ M ≦ 100)이 주어집니다.

세 번째 줄에는 M개의 정수 A1, A2, ...,  AM 이 공백을 사이에 두고 주어집니다. i번째 (1 ≦ i ≦ M) 게임의 타겟이 친구 Ai (1 ≦ Ai ≦ N) 라는 것을 나타냅니다.

이어지는 M개의 줄 중 i(1 ≦ i ≦ M)번째 줄에는, N개의 정수 Bi,1, Bi,2, ..., Bi,N가 공백을 사이에 두고 주어집니다. 이것은 i번째 게임에서 친구 j(1 ≦ j ≦ N)가 친구 Bi,j (1 ≦ Bi,j ≦ N)의 이름을 종이에 썼다는 것을 의미합니다. 타겟은 자신의 이름을 종이에 쓰도록 되어 있으므로, j = Ai 이면, 반드시 Bi,j = j입니다.

출력

M번의 게임에서, 각각의 친구들이 얻은 합계 점수를 출력하세요.

총 N줄의 출력에서,  j번째 (1 ≦ j ≦ N) 줄에는 친구 j의 합계 점수를 출력하세요.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

힌트

예제 1의 경우, 3명의 친구가 4번의 게임을 합니다.

• 첫 번째 게임의 타겟은 '친구 1'이므로, 친구 1 은 2점, 친구 2 는 1점, 친구 3 은 0점을 얻습니다.
• 두 번째 게임의 타겟은 '친구 2'이므로, 친구 1 은 0점, 친구 2 는 2점, 친구 3 은 1점을 얻습니다.
• 세 번째 게임의 타겟은 '친구 3'이므로, 친구 1 은 0점, 친구 2 는 0점, 친구 3 은 3점을 얻습니다.
• 네 번째 게임의 타겟은 '친구 2'이므로, 친구 1 은 1점, 친구 2 는 1점, 친구 3 은 1점을 얻습니다.

4번의 게임 종료 후의 합계 점수는, 친구 1 은 3점, 친구 2 는 4점, 친구 3은 5점이 됩니다.

#include<stdio.h>
#include<stdlib.h>

int main(void)
{
	int M, N, *friends=NULL, *target=NULL;

	scanf("%d", &N);
	friends=(int *)calloc(N,sizeof(int));

	scanf("%d", &M);
	target=(int *)malloc(M*sizeof(int));

	for(int i=0;i<M;i++)
		scanf("%d", &target[i]);

	for(int i=0;i<M;i++)
	{
		int count=N;

		for(int j=0;j<N;j++)
		{
			int choice;

			scanf("%d", &choice);

			if(target[i]==choice)
			{
				friends[j]++;
				count--;
			}
		}

		friends[target[i]-1]+=count;
	}

	for(int j=0;j<N;j++)
		printf("%d\n", friends[j]);

	free(friends);
	free(target);
	return 0;
}

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

예제 입력 4

예제 출력 4

예제 입력 5

예제 출력 5

#include<stdio.h>
#include<stdbool.h>

bool isPrime(int N)
{
	if(N<2)
		return false;
	else if(N==2)
		return true;
	else if(N%2==0)
		return false;
	else
		for(int i=3;i*i<=N;i+=2)
			if(N%i==0) 
				return false; 
	return true; 
}

void divide(int N)
{
	for(int i=2;i<=N;i++)
		if(N%i==0)
			if(isPrime(i))
			{
				printf("%d\n", i);
				N/=i;
				i--;
			}
	if(N!=1)
		printf("%d\n", N);
}

int main(void) 
{
	int N;

	scanf("%d", &N);

	divide(N);

	return 0;
}

문제

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

입력

첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

예제 입력 1

예제 출력 1

#include<stdio.h>

int main(void)
{
	long long int N;
	int arr[11];

	for(int i=0;i<11;i++)
		arr[i]=-1;

	scanf("%lld", &N);

	for(int i=0;N>0;i++)
	{
		arr[i]=N%10;
		N/=10;
	}

	for(int i=0;arr[i]!=-1;i++)
		for(int j=i+1;arr[j]!=-1;j++)
			if(arr[i]<arr[j])
			{
				int temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
			}

	N=0;

	for(int i=0;arr[i]!=-1;i++)
	{
		N*=10;
		N+=arr[i];
	}

	printf("%lld\n", N);

	return 0;
}