문제

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

입력

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y).

출력

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 2^31-1보다 작거나 같다.

예제 입력 1

2 3
1 2 4
8 16 32
3
1 1 2 3
1 2 1 2
1 3 2 3

예제 출력 1

63
2
36

더보기

Solution

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

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

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

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

	scanf("%d", &K);

	for(int k=0;k<K;k++)
	{
		int i, j, x, y, sum=0;

		scanf("%d %d %d %d", &i, &j, &x, &y);

		for(int n=i-1;n<x;n++)
			for(int m=j-1;m<y;m++)
			sum+=arr[n][m];

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

	for(int n=0;n<N;n++)
		free(arr[n]);
	free(arr);
	return 0;
}
728x90

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

예제 입력 1

3 4
1 2 3 4
0 0 0 5
9 8 7 6

예제 출력 1

31

예제 입력 2

3 3
1 0 0
0 1 0
0 0 1

예제 출력 2

3

예제 입력 3

4 3
1 2 3
6 5 4
7 8 9
12 11 10

예제 출력 3

47

더보기

Solution

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

int maximum(int x,int y,int z)
{
	if(x>=y && x>=z)
		return x;
	else if(y>=x && y>=z)
		return y;
	else
		return z;
}

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

	scanf("%d %d", &N, &M);
	candy=(int **)malloc(N*sizeof(int *));
	for(int r=0;r<N;r++)
		candy[r]=(int *)calloc(M,sizeof(int));
	max=(int **)malloc(N*sizeof(int *));
	for(int r=0;r<N;r++)
		max[r]=calloc(M,sizeof(int));
	for(int r=0;r<N;r++)
		for(int c=0;c<M;c++)
			scanf("%d", &candy[r][c]);

	max[0][0]=candy[0][0];
	for(int r=1;r<N;r++)
		max[r][0]=max[r-1][0]+candy[r][0];
	for(int c=1;c<M;c++)
		max[0][c]=max[0][c-1]+candy[0][c];

	for(int r=1;r<N;r++)
		for(int c=1;c<M;c++)
			max[r][c]=candy[r][c]+maximum(max[r-1][c-1],max[r-1][c],max[r][c-1]);

	printf("%d\n", max[N-1][M-1]);
	for(int r=0;r<N;r++)
		free(max[r]);
	free(max);
	for(int r=0;r<N;r++)
		free(candy[r]);
	free(candy);
	return 0;
}
728x90

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 500이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

예제 입력 1

XXXXXX

예제 출력 1

AAAABB

예제 입력 2

XX.XX

예제 출력 2

BB.BB

예제 입력 3

XXXX....XXX.....XX

예제 출력 3

-1

예제 입력 4

X

예제 출력 4

-1

예제 입력 5

XX.XXXXXXXXXX..XXXXXXXX...XXXXXX

예제 출력 5

BB.AAAAAAAABB..AAAAAAAA...AAAABB

더보기

Solution

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

int main(void)
{
	int start=0;
	char board[501]={'\0', };
	bool error=false;

	scanf("%s", board);

	while(start<strlen(board))
	{
		while(board[start]=='.')
			start++;
		int end=start;
		while(board[end]!='.' && end<strlen(board))
			end++;

		if((end-start)%2!=0)
		{
			error=true;
			printf("-1\n");
			break;
		}

		while(end-start>=4)
			for(int i=0;i<4;i++)
				board[start++]='A';
		while(end-start>=2)
			for(int i=0;i<2;i++)
				board[start++]='B';
	}

	if(!error)
		printf("%s\n", board);
	return 0;
}
728x90

문제

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다. 

6을 예로 들면

  • 6 ÷ 1 = 6 … 0
  • 6 ÷ 2 = 3 … 0
  • 6 ÷ 3 = 2 … 0
  • 6 ÷ 4 = 1 … 2
  • 6 ÷ 5 = 1 … 1
  • 6 ÷ 6 = 1 … 0

그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.

두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

출력

첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력하시오.

예제 입력 1

6 3

예제 출력 1

3

더보기

Solution

#include<stdio.h>

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

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

	for(int i=1;i<=N;i++)
	{
		count+=N%i==0;
		if(count==K)
		{
			printf("%d", i);
			break;
		}
	}

	if(count<K)
		printf("0");

	return 0;
}
728x90

문제

입력 받은 대로 출력하는 프로그램을 작성하시오.

입력

입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시작하지 않고, 공백으로 끝나지 않는다.

출력

입력받은 그대로 출력한다.

예제 입력 1

Hello
Baekjoon
Online Judge

예제 출력 1

Hello
Baekjoon
Online Judge

더보기

Solution

#include<stdio.h>

int main(void)
{
	char str[100][101]={'\0'};
	int N=0;

	while(gets(str[N])!='\0')
		puts(str[N++]);

	return 0;
}

 

728x90

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

예제 입력 1

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

예제 출력 1

1

예제 입력 2

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

예제 출력 2

12

더보기

Solution

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

int main(void)
{
	int N, M, min=64;
	char **board=NULL;

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

	for(int i=0;i+7<N;i++)
		for(int j=0;j+7<M;j++)
		{
			int difference, white=0, black=0;

			for(int x=0;x<8;x++)
				for(int y=0;y<8;y++)
				{
					white+=(x+y)%2==0?board[i+x][j+y]=='W':board[i+x][j+y]=='B';
					black+=(x+y)%2==0?board[i+x][j+y]=='B':board[i+x][j+y]=='W';
				}

			difference=white<black?white:black;
			min=difference<min?difference:min;
		}

	printf("%d\n", min);
	for(int i=0;i<N;i++)
		free(board[i]);
	free(board);
	return 0;
}
728x90

문제

19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다.

택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다.

D(T1,T2) = |x1-x2| + |y1-y2|

두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다.

따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다.

원: 평면 상의 어떤 점에서 거리가 일정한 점들의 집합

반지름 R이 주어졌을 때, 유클리드 기하학에서 원의 넓이와, 택시 기하학에서 원의 넓이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 반지름 R이 주어진다. R은 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다.

예제 입력 1

1

예제 출력 1

3.141593
2.000000

힌트

유클리드 기하학: 한국어 위키 영문 위키 Wolfram Mathworld

비유클리드 기하학: 한국어 위키 영문 위키 Wolfram Mathworld

택시 기하학: 한국어 위키 영문 위키 Wolfram Mathworld


더보기

Solution

#include<stdio.h>

int main(void)
{
	int R;

	scanf("%d", &R);

	printf("%lf\n%lf\n", 3.141592653589*R*R, (double)2*R*R);
	return 0;
}
728x90

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1

7 3

예제 출력 1

<3, 6, 2, 7, 5, 1, 4>

더보기

Solution

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

int main(void)
{
	int N, K, front=0, rear, *Y=NULL;

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

	for(rear=0;rear<N;rear++)
		Y[rear]=rear+1;

	printf("<");
	for(int n=0;n<N;n++)
	{
		for(int k=1;k<K;k++)
			Y[(rear++)%N]=Y[(front++)%N];
		printf("%d", Y[(front++)%N]);
		printf("%s", n==N-1?">":", ");
	}

	free(Y);
	return 0;
}

 

728x90

+ Recent posts