whitespace

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1

예제 출력 1

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

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

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

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

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

	qsort((void *)A,(size_t)N,sizeof(int),compare);

	scanf("%d", &M);

	for(int i=0;i<M;i++)
	{
		int number;
		bool found=false;

		scanf("%d", &number);

		if(number<=A[N/2])
		{
			for(int j=0;A[j]<=number;j++)
				if(A[j]==number)
				{
					found=true;
					break;
				}
		}
		else
			for(int j=N-1;A[j]>=number;j--)
				if(A[j]==number)
				{
					found=true;
					break;
				}

		printf("%d\n", found);
	}

	free(A);
	return 0;
}

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

#include<stdio.h>

int main(void)
{
	int n;

	scanf("%d", &n);

	if(n==1 || n==3)
		printf("-1\n");
	else
	{
		switch(n%10)
		{
			case 0:
			case 5:
				printf("%d\n", n/5);
				break;
			case 1:
			case 3:
				printf("%d\n", (n-10-(n%10))/5+4+(n%10)/2);
				break;
			case 2:
			case 4:
				printf("%d\n", n/5+(n%10)/2);
				break;
			case 6:
			case 8:
				printf("%d\n", (n-(n%10))/5+(n%10)/2);
				break;
			case 7:
			case 9:
				printf("%d\n", n/5+((n-5)%10)/2);
				break;
		}
	}

	return 0;
}

문제

베스킨라빈스 게임은 1부터 31까지의 수를 순차적으로 한번에 1~3개까지 연달아 부를 수 있으며, 마지막 31을 부른 사람이 지는 게임이다. 시온이와 민우는 베스킨라빈스 게임을 하기로 했지만 이 게임이 너무 유명한 나머지 시온이와 민우 모두 필승 방법을 알고 있었다. 평소에 항상 운이 없던 시온이는 가위바위보를 져 민우에게 선공을 빼았기게 되었고 이대로 게임을 한다면 질 수밖에 없는 상황이다. 그래서 시온이는 1~3개의 수가 아닌 1~n까지의 수를 부를 수 있는 규칙의 게임으로 변형하자고 말하였고 민우도 수락했다.

이 경우 시온이가 게임을 이길 수 있는 모든 n(1 ≤ n ≤ A)을 출력하시오.

입력

첫 번째 줄에 A이 주어진다. (1 ≤ A ≤ 31)

출력

각 줄에 시온이가 게임을 이길 수 있는 n을 한 줄에 하나씩 오름차순으로 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

#include<stdio.h>

int main(void)
{
	int A;

	scanf("%d", &A);

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

	return 0;
}

문제

태영이의 취미는 2의 제곱수를 계산하는 것이다.

태영이는 2^64 = 18,446,744,073,709,551,616 이라는 것을 알고 있고 직접 20부터 2씩 곱해서 264을 구할 것이다.

하지만 태영이는 2씩 곱하는 와중에 1을 빼버리는 실수를 딱 한 번 해버리고 말았다. (실수는 단 한 번만 하며, 그 후에는 2로 곱하는 계산을 정확하게 수행한다.)

예를 들어, 2^1 = 2로 계산을 잘 하다가 2^2 = 3으로 계산해버리는 어이없는 실수를 해버리는 것이다.

그렇게 된다면 2^3 = 6 , 2^4 = 12 ... 로 계산하여 점점 오차가 커진다.

태영이가 구한 2^64인 N이 주어졌을 때, 태영이가 처음으로 실수한 구간을 찾아주자.

입력

양의 정수 N이 주어진다.

N은 태영이가 2^64를 계산했을 때 나올 수 있는 수이다.

출력

태영이가 처음으로 실수한 구간을 찾아주자.

2K = 2K-1로 계산해버렸을 때의 K를 출력하면 된다.

제한

• 2 ≤ N ≤ 18,446,744,073,709,551,615 = 2^64 - 1

예제 입력 1

예제 출력 1

2^63 = 9,223,372,036,854,775,808 까지는 계산을 잘 하다가

2^64를 2^64-1인 18,446,744,073,709,551,615로 계산을 잘못해버렸다. 

#include<stdio.h>

int main(void)
{
	unsigned long long int N;
	int K=64;

	scanf("%llu", &N);

	while(N%2==0)
	{
		N/=2;
		K--;
	}

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

문제

0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라. 

예를 들어 수열 1 2 2 4 4 5 7 7 2 의 경우에는  1≤2≤2≤4≤4≤5≤7≤7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4 1 3 3 2 2 9 2 3 의 경우에는 3≥3≥2≥2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1 5 3 6 4 7 1 3 2 9 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다.

입력

첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.

출력

첫째 줄에 가장 긴 길이를 출력한다.

예제 입력 1

예제 출력 1

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

int main(void)
{
	int count=1, max=1, N, *arr=NULL;

	scanf("%d", &N);
	arr=(int *)malloc(N*sizeof(int));
	for(int i=0;i<N;i++)
		scanf("%d", &arr[i]);

	for(int i=1;i<N;i++)
		if(arr[i]>=arr[i-1])
		{
			count++;
			max=max>count?max:count;
		}
		else
			count=1;
	count=1;
	for(int i=1;i<N;i++)
		if(arr[i]<=arr[i-1])
		{
			count++;
			max=max>count?max:count;
		}
		else
			count=1;

	printf("%d\n", max);
	free(arr);
	return 0;
}

문제

2020 INPC는 IGRUS 뉴비들을 위해 열리는 대회입니다. 하지만 영수 할아버지나 인용 할아버지와 같이 14학번이지만 마음만은 뉴비인 어르신들 때문에 대회장이 TLE들의 파티가 되자 뉴비의 기준을 정의하기로 하였습니다.

INPC 운영진들은 고심 끝에 뉴비를 1학년 혹은 2학년인 학생으로 정의 내렸고 뉴비를 정의하는 김에 올드비와 TLE도 정의 내리기로 하였습니다. 올드비는 N학년 이하이면서 뉴비가 아닌 학생으로 정의하기로 하였고 TLE은 뉴비도 아니고 올드비도 아닌 학생으로 정의하였습니다.

N과 M이 주어졌을 때, M학년이 뉴비인지 올드비인지 TLE인지 구별해 주세요.

입력

양의 정수 N과 M이 공백을 사이에 두고 주어집니다.

출력

M학년이 뉴비라면 NEWBIE!를, 올드비라면 OLDBIE!를 TLE이라면 TLE!을 출력합니다.

제한

• 3 ≤ N ≤ 1,000
• 1 ≤ M ≤ 1,000

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

힌트

TLE은 Time Limit Exceeded의 약자입니다.

#include<stdio.h>

int main(void)
{
	int N, M;

	scanf("%d %d", &N, &M);

	if(M<3)
		printf("NEWBIE!\n");
	else if(M<=N)
		printf("OLDBIE!\n");
	else
		printf("TLE!\n");

	return 0;
}

문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

입력

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

출력

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

예제 입력 1

예제 출력 1

#include<stdio.h>

int main(void)
{
	int N, count, bound=1;

	scanf("%d", &N);

	for(count=1;bound<N;count++)
		bound+=6*count;

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

	return 0;
}

문제

2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다.

주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 

• 1년마다 5%의 이율을 얻는 투자 (A)
• 3년마다 20%의 이율을 얻는 투자 (B)
• 5년마다 35%의 이율을 얻는 투자 (C)

투자를 할 때에는 다음과 같은 주의점이 있다.

• 투자의 기한(1년, 3년, 5년)을 채우는 시점에 이율이 반영되며, 그 사이에는 돈이 늘어나지 않는다.
• 투자 방식은 매년 바꿀 수 있다.
• 매번 이율은 소수점 이하를 버림 해서 받는다.

예를 들어서, 지금 가진 돈이 11111원이면, A 방식이면 1년 후에 555원, B 방식이면 3년 후에 2,222원, C 방식이면 5년 후에 3,888원을 이자로 받을 수 있다. 만약 C 방식으로 투자했지만 4년이 지난 시점이라면 받을 수 있는 이자는 0원이다.

주형이의 초기 비용이 H원일 때, Y년이 지난 시점에 가장 많은 금액을 얻을 수 있는 투자 패턴을 분석하고 그 금액을 출력하자.

입력

첫째 줄에 초기 비용 H와 투자 기간 Y가 주어진다.

모든 입력은 정수로 주어진다.

출력

가장 많은 이득을 얻었을 때의 총 자산을 소수점을 모두 버리고 정수로 출력한다.

제한

• 10,000 ≤ H ≤ 100,000, H는 정수
• 0 ≤ Y ≤ 10, Y는 정수

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

#include<stdio.h>

int main(void)
{
	int H, Y;

	scanf("%d %d", &H, &Y);

	switch(Y)
	{
		case 1:
		case 2:
		case 3:
		case 6:
		case 9:
				for(int A=0;A<Y%3;A++)
					H*=1.05;
				for(int B=3;B<=Y;B+=3)
					H*=1.2;
				break;
		case 5:
		case 10:
				for(int C=5;C<=Y;C+=5)
					H*=1.35;
				for(int B=0;B<Y%5;B+=3)
					H*=1.2;
				break;
		case 4:
		{
				int compare[2];

				compare[0]=compare[1]=H;
				for(int i=0;i<2;i++)
					for(int j=0;j<2;j++)
						compare[j]*=i==j?1.05:1.2;
				H=compare[0]>compare[1]?compare[0]:compare[1];
				break;
		}
		case 7:
		{
				int compare[3];

				compare[0]=compare[1]=compare[2]=H;
				for(int i=0;i<3;i++)
					for(int j=0;j<3;j++)
						compare[j]*=i==j?1.05:1.2;
				for(int i=0;i<3;i++)
					H=compare[i]>H?compare[i]:H;
				break;
		}
		case 8:
		{
				int compare[2];

				compare[0]=compare[1]=H;
				for(int i=0;i<2;i++)
					for(int j=0;j<2;j++)
						compare[j]*=i==j?1.35:1.2;
				H=compare[0]<compare[1]?compare[1]:compare[0];
				break;
		}
		default:
				break;
	}

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

	return 0;
}