whitespace

문제

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

입력

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

출력

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

예제 입력 1

예제 출력 1

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

int main(void)
{
	unsigned int T, n, *way=calloc(1000001,sizeof(unsigned int));

	way[0]=0;
	way[1]=1;
	way[2]=2;
	way[3]=4;
	for(int w=4;w<1000001;w++)
		way[w]=(way[w-1]+way[w-2]+way[w-3])%1000000009;

	scanf("%u", &T);

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

	free(way);
	return 0;
}

문제

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

예제 입력 1

예제 출력 1

#include<stdio.h>
#include<string.h>

int main(void)
{
	char S[1000001]={'\0', };
	int zero=0, one=0;

	scanf("%s", S);

	for(int s=1;s<strlen(S);s++)
		if(S[s]!=S[s-1])
		{
			if(S[s-1]=='0')
				zero++;
			else
				one++;
		}
	if(S[strlen(S)-1]=='0')
		zero++;
	else
		one++;

	printf("%d\n", zero>one?one:zero);
	return 0;
}

문제

상근이는 선영이와 함께 게임을 하고 있다. 먼저, 상근이는 두 양의 정수 A와 B를 고른다. (1 ≤ B ≤ A ≤ 500) 그 다음, 선영이는 상근이가 고른 수를 맞춰야 한다.

상근이는 선영이에게 다음과 같은 힌트를 주었다.

A의 제곱은 B의 제곱보다 N만큼 커 (1 ≤ N ≤ 1,000)

위의 힌트 조건을 만족하는 A와 B 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

상근이의 힌트 조건을 만족하는 (A,B) 쌍의 개수를 출력한다. 

예제 입력 1

예제 출력 1

#include<stdio.h>

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

	scanf("%d", &N);

	for(int B=1;B<=500;B++)
		for(int A=B;A*A-B*B<=N;A++)
			count+=A*A-B*B==N;

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

문제

숫자 맞추기 게임은 초등학교 학생들 사이에서 유행하는 게임이다. 선생님은 학생들의 연산 실력과 논리적인 사고력을 기르기위해 학생들에게 이 게임을 권유하고 있다.

이 게임을 시작할 때는 친구가 숫자 하나를 머리속에 생각해야 한다. 이 숫자를 n(0)이라고 하자. 그러고 나서 다음과 같이 게임을 진행한다.

1. 친구에게 n(1) = 3*n(0) 계산을 하라고 한 뒤, n(1)이 짝수인지 홀수인지를 말해달라고 한다.
2. n(1)이 짝수라면, n(2) = n(1)/2를, 홀수라면 n(2) = (n(1)+1)/2를 계산해달라고 한다.
3. n(3) = 3*n(2)의 계산을 부탁한다.
4. 친구에게 n(4) = n(3)/9를 계산한 뒤, 그 값을 말해달라고 한다. (n(4)는 나눗셈의 몫이다)
5. 자 이제, n1이 짝수였다면, n(0) = 2*n(4)로, 홀수였다면, n(0) = 2*n(4)+1로 처음 친구가 생각한 숫자를 맞출 수 있다.

예를 들어,  친구가 생각한 수가 n(0)=37이었다면, n(1) = 111이 되고 홀수이다. 그 다음 n(2) = 56, n(3) = 168, n(4) = 18이 된다. 친구는 n(4)를 알려주게 된다. 

그럼 2*n(4)+1 = 37이기 때문에, 친구가 제일 처음 생각한 숫자를 맞출 수 있다.

n(0)이 주어졌을 때, n(1)이 홀수인지 짝수인지와 n(4)를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n(0)으로 이루어져 있다. (0 < n(0) < 1,000,000) 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 케이스 번호를 출력하고 n(1)이 짝수라면 'even', 홀수라면 'odd'를 출력하고, n4를 출력한다.

예제 입력 1

예제 출력 1

#include<stdio.h>

int main(void)
{
	int n[5];

	scanf("%d", &n[0]);

	for(int i=1;n[0]!=0;i++)
	{
		n[1]=3*n[0];
		n[2]=(n[1]+1)/2;
		n[3]=3*n[2];
		n[4]=n[3]/9;

		printf("%d. %s %d\n", i, n[1]%2==0?"even":"odd", n[4]);
		scanf("%d", &n[0]);
	}

	return 0;
}

문제

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.

심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

입력

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3≤N≤100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 100,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르다.

출력

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

예제 입력 1

예제 출력 1

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

int compare(const void *x,const void *y)
{
	return *(int *)x>*(int *)y?1:*(int *)x==*(int *)y?0:-1;
}

int gcd(int x,int y)
{
	if(x<y)
	{
		int temp=x;
		x=y;
		y=temp;
	}

	while(y!=0)
	{
		int temp=x%y;
		x=y;
		y=temp;
	}

	return x;
}

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

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

	for(int n=0;n<N;n++)
		scanf("%d", &colonnade[n]);
	qsort((void *)colonnade,(size_t)N,sizeof(int),compare);

	gcd_num=gcd(colonnade[1]-colonnade[0],colonnade[2]-colonnade[1]);
	for(int i=3;i<N;i++)
		gcd_num=gcd(gcd_num,colonnade[i]-colonnade[i-1]);

	printf("%d\n", (colonnade[N-1]-colonnade[0])/gcd_num-N+1);
	free(colonnade);
	return 0;
}

문제

세 대각선이 한 점에서 만나지 않는 볼록 N각형이 주어졌을 때, 대각선의 교차점의 개수를 세는 프로그램을 작성하시오.

아래 그림은 위의 조건을 만족하는 한 육각형의 교차점 그림이다.

모든 내부각이 180도보다 작은 다각형을 볼록 다각형이라고 한다.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 100)

출력

첫째 줄에 교차점의 개수를 출력한다.

예제 입력 1

예제 출력 1

#include<stdio.h>

int main(void)
{
	int N, diagonal=1;

	scanf("%d", &N);

	for(int i=0;i<4;i++)
		diagonal*=(N-i);
	diagonal/=24;

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

문제

양의 정수 N이 주어졌을 때, 이 수를 소인수분해 한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다.

출력

각 테스트 케이스마다 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력한다. 출력 순서는 인수가 증가하는 순으로 한다.

예제 입력 1

예제 출력 1

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.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 test_case;

	scanf("%d", &test_case);

	for(int t=0;t<test_case;t++)
	{
		int N, *fac=NULL, temp;

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

		for(temp=2;temp<=N;temp++)
			if(N%temp==0)
				if(isPrime(temp))
				{
					fac[temp]++;
					N/=temp;
					temp--;
				}
		if(N!=1)
			fac[N]++;

		for(int i=2;i<=temp;i++)
			if(fac[i]!=0)
				printf("%d %d\n", i, fac[i]);
		free(fac);
	}

	return 0;
}

문제

자연수 n개가 주어진다. 이 자연수의 공약수를 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 2 또는 3이다. 둘째 줄에는 공약수를 구해야 하는 자연수 n개가 주어진다. 모든 자연수는 10^8 이하이다.

출력

입력으로 주어진 n개 수의 공약수를 한 줄에 하나씩 증가하는 순서대로 출력한다.

예제 입력 1

예제 출력 1

#include<stdio.h>

int gcd(int x,int y)
{
	if(x<y)
	{
		int temp=x;
		x=y;
		y=temp;
	}

	while(y!=0)
	{
		int temp=x%y;
		x=y;
		y=temp;
	}

	return x;
}

int main(void)
{
	int n, num[3], gcd_num;

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

	gcd_num=n==2?gcd(num[0],num[1]):gcd(gcd(num[0],num[1]),num[2]);

	for(int i=1;i<=gcd_num;i++)
		if(gcd_num%i==0)
			printf("%d\n", i);

	return 0;
}