whitespace

문제

웨이트 트레이닝에서의 3대 측정은 스쿼트, 벤치프레스, 데드리프트의 중량을 측정하는 것이다. 하지만 세 명이 한 팀을 이루어 출전하는 전국 대학생 프로그래밍 대회(ICPC)의 참가자들은 다소 독특한 방법으로 3대를 측정하는데, 바로 팀원 각각의 실력을 수치로 나타내 주는 ‘코드포스 레이팅’을 비교하는 것이다.

웨이트 트레이닝계에는 3대 중량을 합쳐 500kg를 넘지 못하는 사람은 ‘언더아머’ 브랜드의 옷을 입지 못한다는 암묵적인 룰이 있으며. 이들을 단속하는 ‘언더아머 단속반’이 존재한다는 소문도 있다. Sogang ICPC Team은 이를 벤치마킹해 팀원 3명의 코드포스 레이팅의 합이 K 미만인 팀은 가입할 수 없는 VIP 클럽을 만들고자 한다.

하지만 이런 조건에서는 세 명 중 한 명의 레이팅이 현저히 낮더라도 나머지 두 명의 레이팅이 충분히 높다면 세 명이 모두 VIP 클럽에 가입할 수 있게 된다. 클럽에 가입하는 사람들은 모두 일정 수준 이상이어야겠다고 판단한 학회장 임지환은 모든 팀원의 레이팅이 L 이상이고, 팀원 세 명의 레이팅의 합이 K 이상인 팀만이 가입할 수 있게 하였다.

학회 일과 연합 일에 치여 사는 지환이는 VIP 클럽의 회원 관리까지 할 시간이 없다. 지환이를 위해 지원자 중 VIP 클럽에 가입할 수 있는 팀의 수를 구하고, VIP 회원들의 레이팅을 출력해 보자.

입력

첫째 줄에 정수 N, K, L이 주어진다. N은 팀의 수, K는 팀원 3명의 레이팅 합에 대한 클럽 가입 조건, L은 개인 레이팅에 대한 클럽 가입 조건이다. (1≤N≤500 000, 0≤K≤12 000, 0≤L≤4 000)

둘째 줄부터 N개 줄에 VIP 클럽에 신청한 팀의 팀원들의 레이팅 정보를 나타내는 정수 x1, x2, x3이 한 줄에 한 팀씩 주어진다. (0≤x1,x2,x3≤4 000)

출력

첫째 줄에 VIP 클럽에 가입이 가능한 팀의 수를 출력한다.

둘째 줄에 VIP 회원들의 레이팅을 입력받은 순서대로 공백으로 구분해 하나씩 출력한다.

예제 입력 1

예제 출력 1

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

int main(void)
{
	int N, K, L, **VIP=NULL, count=0;

	scanf("%d %d %d", &N, &K, &L);
	VIP=(int **)malloc(N*sizeof(int *));
	for(int n=0;n<N;n++)
		VIP[n]=(int *)malloc(4*sizeof(int));

	for(int n=0;n<N;n++)
	{
		for(int i=0;i<3;i++)
			scanf("%d", &VIP[n][i]);
		VIP[n][3]=VIP[n][0]>=L&&VIP[n][1]>=L&&VIP[n][2]>=L&&VIP[n][0]+VIP[n][1]+VIP[n][2]>=K;
		count+=VIP[n][3];
	}

	printf("%d\n", count);
	for(int n=0;n<N;n++)
		if(VIP[n][3])
			printf("%d %d %d ", VIP[n][0], VIP[n][1], VIP[n][2]);
	printf("\n");
	for(int n=0;n<N;n++)
		free(VIP[n]);
	free(VIP);
	return 0;
}

문제

단색 비트맵 이미지는 이미지를 구성하는 각 픽셀은 0 또는 1의 색상 정보를 가지고 있다.

비트맵 이미지는 생성 당시 이미지의 크기, 해당 이미지를 구성하는 모든 픽셀의 정보가 이미 정해져 있기 때문에, 그림 1과 같이 이미지의 크기를 늘리더라도

기존의 픽셀이 늘린 방향으로 넓게 퍼질 뿐 해상도가 늘어나진 않는다.

< 그림 1. 크기를 늘린 비트맵 이미지의 예시 >

이렇게 기존에 있던 이미지에 픽셀을 추가하여 그림을 구성하는 총 픽셀 수를 늘리는 것을 업샘플링 (Up sampling) 이라고 한다.

업샘플링을 하는 방법은 여러 가지가 있는데 그중 가장 간단한 방법은 기존 픽셀의 배열을 그대로 유지한 채, 각 픽셀의 개수를 동일하게 늘리는 방법이다.

<그림 2. 그림을 가로, 세로로 K(=2) 배 늘렸을 때 추가된 픽셀의 모습 >

가로 세로의 길이가 N 인 단색 비트맵 이미지를 구성하는 모든 픽셀의 정보가 주어질 때, 해당 그림의 가로와 세로 크기를 그림 2와 같이 K 배 늘렸을 때, 업샘플링을 통해 늘어난 그림의 픽셀 정보들을 구해보자.

입력

첫 번째 줄에는 정사각형 단색 비트맵의 가로/세로 길이 N (1 ≤ N ≤ 10)과 이미지를 늘릴 배수 K (1 ≤ K ≤ 10) 가 주어진다.

두 번째 줄부터 (N+1)번째 줄에는 각 줄마다 N개의 픽셀 정보가 주어진다.

출력

N x K 줄에 걸쳐, 늘어난 단색 비트맵 이미지의 픽셀 정보를 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

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

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

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

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

	for(int i=0;i<N;i++)
		for(int ki=0;ki<K;ki++)
		{
			for(int j=0;j<N;j++)
				for(int kj=0;kj<K;kj++)
					printf("%d ", image[i][j]);
			printf("\n");
		}
	for(int n=0;n<N;n++)
		free(image[n]);
	free(image);
	return 0;
}

문제

쿠키런은 데브시스터즈에서 제작한 모바일 러닝 액션 게임이다. 마녀의 오븐에서 탈출한 쿠키들과 함께 모험을 떠나는 게임으로, 점프와 슬라이드 2가지 버튼만으로 손쉽게 플레이할 수 있는 것이 특징이다.

연세대학교를 졸업한 김강산 선배님이 데브시스터즈에 취직하면서 주변 사람들에게 쿠키런을 전파시켰다. 하지만 게임을 전파하던 중에 쿠키들에게 신체적으로 이상이 생기는 것을 발견하였다. 팔, 다리 길이가 임의적으로 변한 것이다. 때문에 긴급하게 각 쿠키들의 신체들을 측정하려고 한다.

쿠키들은 신체를 측정하기 위해서 한 변의 길이가 N인 정사각형 판 위에 누워있으며, 어느 신체 부위도 판 밖으로 벗어나지 않는다. 판의 x번째 행, y번째 열에 위치한 곳을 (x, y)로 지칭한다. 판의 맨 왼쪽 위 칸을 (1, 1), 오른쪽 아래 칸을 (N, N)으로 나타낼 수 있다.

그림과 같이 쿠키의 신체는 머리, 심장, 허리, 그리고 좌우 팔, 다리로 구성되어 있다. 그림에서 빨간 곳으로 칠해진 부분이 심장이다. 머리는 심장 바로 윗 칸에 1칸 크기로 있다. 왼쪽 팔은 심장 바로 왼쪽에 붙어있고 왼쪽으로 뻗어 있으며, 오른쪽 팔은 심장 바로 오른쪽에 붙어있고 오른쪽으로 뻗어있다. 허리는 심장의 바로 아래 쪽에 붙어있고 아래 쪽으로 뻗어 있다. 왼쪽 다리는 허리의 왼쪽 아래에, 오른쪽 다리는 허리의 오른쪽 아래에 바로 붙어있고, 각 다리들은 전부 아래쪽으로 뻗어 있다. 각 신체 부위들은 절대로 끊겨있지 않으며 굽혀진 곳도 없다. 또한, 허리, 팔, 다리의 길이는 1 이상이며, 너비는 무조건 1이다.

쿠키의 신체가 주어졌을 때 심장의 위치와 팔, 다리, 허리의 길이를 구하여라.

입력

다음과 같이 입력이 주어진다.

출력

첫 번째 줄에는 심장이 위치한 행의 번호 x와 열의 번호 y를 공백으로 구분해서 출력한다.

두 번째 줄에는 각각 왼쪽 팔, 오른쪽 팔, 허리, 왼쪽 다리, 오른쪽 다리의 길이를 공백으로 구분해서 출력하여라.

제한

• 5 ≤ N ≤ 1,000. N은 판의 한 변의 길이를 의미하는 양의 정수다.
• a(i,j)는 * 또는 _이다. *는 쿠키의 신체 부분이고, _는 쿠키의 신체가 올라가 있지 않은 칸을 의미한다. (1 ≤ i, j ≤ N)
• 쿠키의 신체 조건에 위배되는 입력은 주어지지 않는다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

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

int main(void)
{
	int N, heart[2]={-1,-1}, size[5]={0, };
	char **square=NULL;

	scanf("%d", &N);
	square=(char **)malloc(N*sizeof(char *));
	for(int n=0;n<N;n++)
	{
		square[n]=(char *)calloc(N+1,sizeof(char));
		scanf("%s", square[n]);
	}

	for(int i=0;heart[0]==-1&&heart[1]==-1;i++)
		for(int j=0;j<N;j++)
			if(square[i][j]=='*')
			{
				heart[0]=i+1;
				heart[1]=j;
				break;
			}

	for(int n=1;heart[1]-n>=0 && square[heart[0]][heart[1]-n]=='*';n++)
		size[0]++;
	for(int n=heart[1]+1;n<N && square[heart[0]][n]=='*';n++)
		size[1]++;
	for(int n=heart[0]+1;n<N && square[n][heart[1]]=='*';n++)
		size[2]++;
	for(int n=heart[0]+size[2]+1;n<N && square[n][heart[1]-1]=='*';n++)
		size[3]++;
	for(int n=heart[0]+size[2]+1;n<N && square[n][heart[1]+1]=='*';n++)
		size[4]++;

	printf("%d %d\n", heart[0]+1, heart[1]+1);
	for(int i=0;i<5;i++)
		printf("%d ", size[i]);
	printf("\n");
	for(int n=0;n<N;n++)
		free(square[n]);
	free(square);
	return 0;
}

문제

국렬이는 모르고리즘 차기 회장을 빠르게 구해야 한다. 안 그러면 대학원 가서도 회장을 해야 하기 때문이다.

그래서 국렬이는 어떻게든 2020년 연세대학교 프로그래밍 경진대회를 열어서 차기 회장을 선택하려고 했으나, 코로나19 때문에 미루고 결국 11월에 개최하게 되었다.

국렬이는 대회를 치른 사람 중에서 점수가 가장 높은 사람을 억지로 차기 회장으로 지목하려고 한다. 만약에 가장 높은 사람이 2명 이상 있는 경우, 이름이 사전 순으로 가장 앞선 사람을 차기 회장으로 뽑을 것이다.

차기 회장으로 누가 지목될지 알아내라.

입력

다음과 같이 입력이 주어진다.

출력

첫째 줄에 차기 회장으로 뽑힐 사람의 이름을 출력하여라.

제한

• 1 ≤ N ≤ 100,000. N은 사람의 수를 나타내는 양의 정수다.
• Ai는 길이가 1 이상 10 이하의 알파벳 소문자로 구성된 문자열로 참여자의 이름이다. (1 ≤ i ≤ N)
• Ai ≠ Aj (1 ≤ i < j ≤ N)
• 1 ≤ Bi ≤ 1,000,000,000 (1 ≤ i ≤ N). Bi는 점수를 의미하는 양의 정수다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

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

int main(void)
{
	int N, maxB=0, B;
	char maxA[11], A[11];

	scanf("%d", &N);

	for(int n=0;n<N;n++)
	{
		scanf("%s %d", A, &B);

		if(B>maxB || B==maxB && strcmp(A,maxA)<0)
		{
			maxB=B;
			strcpy(maxA,A);
		}
	}

	printf("%s\n", maxA);
	return 0;
}

문제

수 N개가 주어졌을 때, N개의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 100)개의 수가 공백으로 구분되어서 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 또, 0으로 시작하는 수는 주어지지 않는다.

출력

입력받은 수 N개의 합을 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

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

int main(void)
{
	char N[601]={'\0', };
	int num=0, sum=0;

	fgets(N,sizeof(N),stdin);

	for(int n=0;n<strlen(N);n++)
		if(N[n]>='0' && N[n]<='9')
		{
			num*=10;
			num+=N[n]-'0';
		}
		else
		{
			sum+=num;
			num=0;
		}

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

문제

크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.

여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자. 즉, max(1 ≤ i ≤  j ≤ N) (X[i]+...+X[j])를 구하자.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)

그리고 두 번째 줄에 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다.

출력

각 테스트케이스 별로 maximum subarray의 합을 줄로 구분하여 출력한다.

예제 입력 1

예제 출력 1

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

int maximum_subarray(int *arr,int size)
{
	int sum=0, max=arr[0];

	for(int i=0;i<size;i++)
	{
		sum=arr[i]+sum>arr[i]?arr[i]+sum:arr[i];
		max=max>sum?max:sum;
	}

	return max;
}

int main(void)
{
	int T;

	scanf("%d", &T);

	for(int t=0;t<T;t++)
	{
		int N, *X=NULL;

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

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

		printf("%d\n", maximum_subarray(X,N));
		free(X);
	}

	return 0;
}

문제

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.

예를 들어, 1234는 줄어들지 않는다. 

줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)이 주어진다. 각 테스트 케이스는 숫자 하나 n으로 이루어져 있다. (1 <= n <= 64)

출력

각 테스트 케이스에 대해 한 줄에 하나씩 줄어들지 않는 n자리 수의 개수를 출력한다.

예제 입력 1

예제 출력 1

#include<stdio.h>

int main(void)
{
	int T, n;

	scanf("%d", &T);

	for(int t=0;t<T;t++)
	{
		long int combination=1;

		scanf("%d", &n);

		for(int N=n+9,r=0;r<9;N--,r++)
			combination*=N;
		for(int r=2;r<10;r++)
			combination/=r;

		printf("%ld\n", combination);
	}

	return 0;
}

문제

N개의 양의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면,

색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다.

입력

첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어진다. 

출력

계산된 최댓값을 소수점 이하 넷째 자리에서 반올림하여 소수점 이하 셋째 자리까지 출력한다.

예제 입력 1

예제 출력 1

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

double maximum_partial_array(double *arr,int size)
{
	double mul=1.0, max=arr[0];

	for(int i=0;i<size;i++)
	{
		mul=arr[i]*mul>arr[i]?arr[i]*mul:arr[i];
		max=max>mul?max:mul;
	}

	return max;
}

int main(void)
{
	int N;
	double *arr=NULL;

	scanf("%d", &N);
	arr=(double *)malloc(N*sizeof(double));

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

	printf("%.3lf\n", maximum_partial_array(arr,N));
	free(arr);
	return 0;
}