whitespace

문제

다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:

• t(0)=1
• t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)

이 정의에 따르면,

• t(1)=t(0)*t(0)=1
• t(2)=t(0)*t(1)+t(1)*t(0)=2
• t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5
• ...

주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다.

출력

첫째 줄에 t(n)을 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

#include<stdio.h>

int main(void)
{
	long int t[36]={1,0};
	int n;

	for(int i=1;i<36;i++)
		for(int j=0;j<i;j++)
			t[i]+=t[j]*t[i-j-1];

	scanf("%d", &n);
	printf("%ld\n", t[n]);
	return 0;
}

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 지난주에 너무 많은 돈을 써 버렸다. 그래서 오늘은 돈을 최소로 지불해서 카드 N개를 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P(1) = 1, P(2) = 5, P(3) = 6, P(4) = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최솟값은 4원이다. 1개 들어있는 카드팩을 4번 사면 된다.

P(1) = 5, P(2) = 2, P(3) = 8, P(4) = 10인 경우에는 카드가 2개 들어있는 카드팩을 2번 사면 4원이고, 이 경우가 민규가 지불해야 하는 금액의 최솟값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 P(i)가 P(1)부터 P(N)까지 순서대로 주어진다. (1 ≤ P(i) ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최솟값을 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

예제 입력 4

예제 출력 4

예제 입력 5

예제 출력 5

예제 입력 6

예제 출력 6

힌트

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

int main(void)
{
	int N, *P=NULL;

	scanf("%d", &N);
	P=(int *)calloc(N+1,sizeof(int));

	for(int n=1;n<=N;n++)
		scanf("%d", &P[n]);

	for(int n=1;n<=N;n++)
		for(int i=1;i<n;i++)
			P[n]=P[i]+P[n-i]<P[n]?P[i]+P[n-i]:P[n];

	printf("%d\n", P[N]);
	free(P);
	return 0;
}

문제

경찰대학 용인캠퍼스에는 나무 한 그루가 있다. 경찰대학생이 떠나간 용인캠퍼스의 토지는 매우 비옥해서 나무가 잘 자란다. 나뭇가지는 나무의 중심 줄기에서 아래와 같은 규칙을 이용해서 뻗어나온다.

1. 나뭇가지는 자랄 때마다 한 번에 2갈래로 갈라지면서 성장한다. 예를 들어, 중심줄기에서 나온 첫 번째 가지의 개수는 2개이며, 두 번째 가지의 총 개수는 첫 번째 가지의 수에 2를 곱해 4개이다.
2. N번째 나뭇가지의 길이는 N-1번째 나뭇가지의 길이의 R/100배이고, 소수점 이하는 버린다. 0번째 나뭇가지는 중심줄기이다.
3. N번째 나뭇가지의 길이가 5cm 이하가 되는 경우, N-1번째 가지에서 성장을 멈춘다.

중심 줄기의 길이 L이 입력으로 주어졌을 때, 중심 줄기를 제외한 나뭇가지의 길이의 합을 구하시오.

입력

첫 번째 줄에 중심 줄기의 길이 L(6 ≤ L ≤ 10,000)이 주어진다. 둘째 줄에 비율 R(1 ≤ R ≤ 99)가 주어진다. L의 단위는 cm이다.

출력

첫 번째 줄에 중심 줄기를 제외한 나뭇가지의 총 길이의 합을 cm단위로 출력하며, 소숫점 이하는 버린다. 총 길이의 합이 10^6보다 작거나 같은 입력만 주어진다.

예제 입력 1

예제 출력 1

1. 1번째 가지의 길이는 ⌊500 × (30/100)⌋ = 150
2. 2번째 가지의 길이는 ⌊150 × (30/100)⌋ = 45
3. 3번째 가지의 길이는 ⌊45 × (30/100)⌋ = 13
4. 4번째 가지의 길이는 ⌊13 × (30/100)⌋ = 3.9 이고, 5cm 이하라서 자라지 않는다.

총 길이의 합은 2×150 + 4×45 + 8×13 = 584cm이다.

#include<stdio.h>

int main(void)
{
	int L, R, sum=0, pow=1;

	scanf("%d", &L);
	scanf("%d", &R);

	while(L>5)
	{
		if(pow!=1)
			sum+=pow*L;
		L*=R;
		L/=100;
		pow*=2;
	}

	printf("%d\n", sum);
	return 0;
}

문제

이 이야기는 고창영이 10살 때 있었던 실화이다.

창영이는 10살 때 파스칼을 독학했다. 창영이가 공부하던 책에는 다음과 같은 프로그램이 있었다.

창영이는 N을 입력했을 때, 무엇이 출력될지 궁금해졌다.

창영이가 입력한 N이 주어졌을 때, 무엇이 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 창영이가 입력한 N이 주어진다. N은 1보다 크거나 같고, 10^9보다 작거나 같은 자연수이다.

출력

첫째 줄에 결과를 출력한다.

예제 입력 1

예제 출력 1

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

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

int main(void)
{
	int N, counter=0;

	scanf("%d", &N);

	if(isPrime(N))
		counter=N-1;
	else if(N%2==0)
		counter=N/2;
	else
	{
		for(int i=3;i<=N;i+=2)
			if(N%i==0)
			{
				counter=N-N/i;
				break;
			}
	}

	printf("%d\n", counter);
	return 0;
}

문제

등차가 정수인 등차수열 (어떤 수에 차례대로 일정한 수를 더해서 이루어지는 수열) 은 2개의 숫자로 나타낼 수 있다. P는 수열의 첫 번째 수이고, Q는 그 다음수가 되기 위해 바로 전의 수에 더해야 하는 수이다. 예를 들어 P=1, Q=2 이면 그 등차수열은 1, 3, 5, 7, ..... 이 된다.

등비가 정수인 등비수열 (어떤 수에서 시작해 차례로 같은 수를 곱하여 만든 수열) 은 등차수열과 비슷하게 2개의 숫자로 나타낼 수 있다. P는 수열의 첫 번째 수이고, Q는 그 다음수가 되기 위해 바로 전의 수에 곱해야 하는 수이다. 예를 들어 P=3, Q=2이면 그 등비수열은 3, 6, 12, ...이 된다.

테디는 세상에서 수학을 제일 좋아해서 매일같이 이 수열이 등차수열인지 등비수열인지 정한다음에 다음 수를 구한다.

어떤 수열이 주어졌을 때, 그 수열의 규칙이 등차수열인지, 등비수열인지 결정한 후에, 다음에 등장할 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 N이 주어진다. 둘째 줄부터 N개의 줄에 수열의 각 원소가 차례대로 주어진다. 주어지는 수열은 등차수열이나 등비수열 중에 하나다. N은 항상 3 이상 50이하이며, 입력되는 수는 10^6 이하의 자연수이다.

출력

첫째 줄에 수열의 다음 원소를 출력한다. 이 수는 20억보다 작거나 같다.

예제 입력 1

예제 출력 1

#include<stdio.h>

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

	scanf("%d", &N);

	for(int n=0;n<3;n++)
		scanf("%ld", &arr[n]);

	if(arr[0]+arr[2]==2*arr[1])
	{
		for(int n=3;n<N;n++)
			scanf("%ld", &arr[2]);
		printf("%ld\n", arr[2]+arr[1]-arr[0]);
	}
	else
	{
		for(int n=3;n<N;n++)
			scanf("%ld", &arr[2]);
		printf("%ld\n", arr[2]*arr[1]/arr[0]);
	}

	return 0;
}

문제

정수론(수학)에서, 세 개의 소수 문제(3-primes problem) 는 다음과 같은 추측을 말한다.

'5보다 큰 임의의 홀수는 정확히 세 개의 소수들의 합으로 나타낼 수 있다. 물론 하나의 소수를 여러 번 더할 수도 있다.'

예를 들면,

• 7 = 2 + 2 + 3
• 11 = 2 + 2 + 7
• 25 = 7 + 7 + 11

5보다 큰 임의의 홀수를 입력받아서, 그 홀수가 어떻게 세 소수의 합으로 표현될 수 있는지 (또는 불가능한지) 알아보는 프로그램을 작성하시오.

입력

첫째 줄에 T(Test Case의 수를 의미함)가 주어진다.

입력은 T개의 Test Case로 이루어진다.

각 Test Case는 하나의 정수 K (7 ≤ K < 1,000, K는 홀수)로 구성된다.

출력

T줄에 걸쳐서, 각 줄에 K가 어떻게 세 소수의 합으로 표현되는지 출력해야 한다.

가능하다면 그 세 소수를 오름차순 정렬하여 출력하면 된다.

여러 개의 답이 가능하다면 그 중 하나만 출력하면 되고, 만약 불가능하다면 0을 출력한다.

예제 입력 1

예제 출력 1

#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 n=3;n*n<=N;n+=2)
			if(N%n==0)
				return false;
	return true;
}

int main(void)
{
	int count=1, prime[167], T, K;

	prime[0]=2;
	for(int i=3;i<997;i+=2)
		if(isPrime(i))
			prime[count++]=i;

	scanf("%d", &T);

	for(int t=0;t<T;t++)
	{
		bool solved=false;

		scanf("%d", &K);

		for(int i=0;prime[i]<K;i++)
		{
			for(int j=i;prime[i]+prime[j]<K;j++)
			{
				for(int k=j;prime[i]+prime[j]+prime[k]<=K;k++)
					if(prime[i]+prime[j]+prime[k]==K)
					{
						solved=true;
						printf("%d %d %d\n", prime[i], prime[j], prime[k]);
					}
				if(solved)
					break;
			}
			if(solved)
				break;
		}

		if(!solved)
			printf("0\n");
	}

	return 0;
}

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n과 m이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 단, 사용한 수의 개수는 m개 이어야 한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n과 m이 주어진다. n은 양수이며 1,000보다 작거나 같다. m도 양수이며, n보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

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

int main(void)
{
	unsigned int **way=NULL;
	int n, m, T;

	way=(unsigned int **)malloc(1001*sizeof(unsigned int *));
	for(int w=0;w<1001;w++)
		way[w]=(unsigned int *)calloc(1001,sizeof(unsigned int));

	way[2][1]=way[3][1]=1;
	for(int w=1;w<1001;w++)
		way[w][w]=1;
	way[3][2]=2;

	for(int i=4;i<1001;i++)
		for(int j=2;j<i;j++)
			way[i][j]=(way[i-1][j-1]+way[i-2][j-1]+way[i-3][j-1])%1000000009;

	scanf("%d", &T);

	for(int t=0;t<T;t++)
	{
		scanf("%d %d", &n, &m);
		printf("%d\n", way[n][m]);
	}

	for(int w=0;w<1001;w++)
		free(way[w]);
	free(way);
	return 0;
}

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제 입력 1

예제 출력 1

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

int main(void)
{
	unsigned int **way=malloc(100001*sizeof(unsigned int *)), T, n;
	for(int w=0;w<100001;w++)
		way[w]=(unsigned int *)calloc(3,sizeof(unsigned int));
	way[0][0]=way[0][1]=way[0][2]=0;
	way[1][0]=1;
	way[1][1]=way[1][2]=0;
	way[2][0]=way[2][2]=0;
	way[2][1]=1;
	way[3][0]=way[3][1]=way[3][2]=1;
	for(int w=4;w<100001;w++)
	{
		way[w][0]=(way[w-1][1]+way[w-1][2])%1000000009;
		way[w][1]=(way[w-2][0]+way[w-2][2])%1000000009;
		way[w][2]=(way[w-3][0]+way[w-3][1])%1000000009;
	}

	scanf("%d", &T);

	for(int t=0;t<T;t++)
	{
		scanf("%d", &n);
		printf("%d\n", (way[n][0]+way[n][1]+way[n][2])%1000000009);
	}

	for(int w=0;w<100001;w++)
		free(way[w]);
	free(way);
	return 0;
}