'백준 알고리즘' 카테고리의 글 목록 (2 Page)

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

예제 입력 1

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

예제 출력 1

27

예제 입력 2

4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2

예제 출력 2

9

예제 입력 3

8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

예제 출력 3

3

Solution

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

int N, M, **lab=NULL;

int simulate()
{
	int queue[64], front=0, rear=0, **test=(int **)malloc(N*sizeof(int *)), count=0, move[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

	for(int n=0;n<N;n++)
	{
		test[n]=(int *)malloc(M*sizeof(int));

		for(int m=0;m<M;m++)
		{
			test[n][m]=lab[n][m];
			if(test[n][m]==2)
				queue[rear++]=10*n+m;
			else if(test[n][m]==0)
				count++;
		}
	}

	while(front<rear)
	{
		int previous_rear=rear;

		while(front<previous_rear)
		{
			for(int i=0;i<4;i++)
			{
				int x=queue[front]/10+move[i][0],  y=queue[front]%10+move[i][1];

				if(x>=0 && x<N && y>=0 && y<M && test[x][y]==0)
				{
					count--;
					queue[rear++]=10*x+y;
					test[x][y]=2;
				}
			}
			front++;
		}
	}

	for(int n=0;n<N;n++)
		free(test[n]);
	free(test);
	return count;
}

int main(void)
{
	int max=0;

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

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

	for(int i=0;i<N*M;i++)
		if(lab[i/M][i%M]==0)
		{
			lab[i/M][i%M]=1;
			for(int j=i+1;j<N*M;j++)
				if(lab[j/M][j%M]==0)
				{
					lab[j/M][j%M]=1;
					for(int k=j+1;k<N*M;k++)
						if(lab[k/M][k%M]==0)
						{
							lab[k/M][k%M]=1;
							int temp=simulate();
							if(temp>max)
								max=temp;
							lab[k/M][k%M]=0;
						}
					lab[j/M][j%M]=0;
				}
			lab[i/M][i%M]=0;
		}

	printf("%d\n", max);
	for(int n=0;n<N;n++)
		free(lab[n]);
	free(lab);
	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 1992번: 쿼드트리 (0)	2023.02.20
<백준 알고리즘> 2630번: 색종이 만들기 (0)	2023.02.20
<백준 알고리즘> 7569번: 토마토 (0)	2023.02.19
<백준 알고리즘> 7576번: 토마토 (0)	2023.02.19
<백준 알고리즘> 15961번: 회전 초밥 (0)	2023.02.16

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력 1

5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

예제 출력 1

-1

예제 입력 2

5 3 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0

예제 출력 2

4

예제 입력 3

4 3 2
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
-1 -1 -1 -1
1 1 1 -1

예제 출력 3

0

Solution

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

int main(void)
{
	int ***tomato=NULL, M, N, H, days=0, count=0, previous_count=0, empty=0, *queue=NULL, front=0, rear=0, move[6][3]={{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1}};

	scanf("%d%d%d", &H, &M, &N);
	queue=(int *)malloc(N*M*H*sizeof(int));
	tomato=(int ***)malloc(N*sizeof(int **));
	for(int i=0;i<N;i++)
	{
		tomato[i]=(int **)malloc(M*sizeof(int *));
		for(int j=0;j<M;j++)
		{
			tomato[i][j]=(int *)malloc(H*sizeof(int));

			for(int k=0;k<H;k++)
			{
				scanf("%d", &tomato[i][j][k]);
				if(tomato[i][j][k]==1)
				{
					count++;
					queue[rear++]=10000*i+100*j+k;
				}
				else if(tomato[i][j][k]==-1)
					empty++;
			}
		}
	}

	while(previous_count<count && N*M*H-empty>count)
	{
		int previous_rear=rear;
		previous_count=count;

		while(front<previous_rear)
		{
			for(int i=0;i<6;i++)
			{
				int x=queue[front]/10000+move[i][0], y=queue[front]/100%100+move[i][1], z=queue[front]%100+move[i][2];

				if(x>=0 && x<N && y>=0 && y<M &&  z>=0 && z<H && tomato[x][y][z]==0)
				{
					queue[rear++]=10000*x+100*y+z;
					tomato[x][y][z]=1;
					count++;
				}
			}
			front++;
		}

		if(count==previous_count && N*M*H-empty!=count)
		{
			days=-1;
			break;
		}
		days++;
	}

	printf("%d\n", count==0?-1:days);
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<M;j++)
			free(tomato[i][j]);
		free(tomato[i]);
	}
	free(tomato);
	free(queue);
	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 2630번: 색종이 만들기 (0)	2023.02.20
<백준 알고리즘> 14502번: 연구소 (0)	2023.02.20
<백준 알고리즘> 7576번: 토마토 (0)	2023.02.19
<백준 알고리즘> 15961번: 회전 초밥 (0)	2023.02.16
<백준 알고리즘> 2531번: 회전 초밥 (0)	2023.02.16

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력 1

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 1

8

예제 입력 2

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 2

-1

예제 입력 3

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

예제 출력 3

6

예제 입력 4

5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

예제 출력 4

14

예제 입력 5

2 2
1 -1
-1 1

예제 출력 5

0

Solution

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

int main(void)
{
	int **tomato=NULL, M, N, days=0, count=0, previous_count=0, empty=0, *queue=NULL, front=0, rear=0, move[4][2]={{-1,0},{0,-1},{0,1},{1,0}};

	scanf("%d%d", &M, &N);
	queue=(int *)malloc(N*M*sizeof(int));
	tomato=(int **)malloc(N*sizeof(int *));
	for(int i=0;i<N;i++)
	{
		tomato[i]=(int *)malloc(M*sizeof(int));
		for(int j=0;j<M;j++)
		{
			scanf("%d", &tomato[i][j]);
			if(tomato[i][j]==1)
			{
				count++;
				queue[rear++]=1000*i+j;
			}
			else if(tomato[i][j]==-1)
				empty++;
		}
	}

	while(previous_count<count && N*M-empty>count)
	{
		int previous_rear=rear;
		previous_count=count;

		while(front<previous_rear)
		{
			for(int i=0;i<4;i++)
			{
				int x=queue[front]/1000+move[i][0], y=queue[front]%1000+move[i][1];

				if(x>=0 && x<N && y>=0 && y<M && tomato[x][y]==0)
				{
					queue[rear++]=1000*x+y;
					tomato[x][y]=1;
					count++;
				}
			}
			front++;
		}

		if(count==previous_count && N*M-empty!=count)
		{
			days=-1;
			break;
		}
		days++;
	}

	printf("%d\n", count==0?-1:days);
	for(int i=0;i<N;i++)
		free(tomato[i]);
	free(tomato);
	free(queue);
	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 14502번: 연구소 (0)	2023.02.20
<백준 알고리즘> 7569번: 토마토 (0)	2023.02.19
<백준 알고리즘> 15961번: 회전 초밥 (0)	2023.02.16
<백준 알고리즘> 2531번: 회전 초밥 (0)	2023.02.16
<백준 알고리즘> 2295번: 세 수의 합 (0)	2023.02.16

문제

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.

원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.

위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.

회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다. 두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d 이하의 정수가 각 줄마다 하나씩 주어진다.

출력

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력한다.

예제 입력 1

8 30 4 30
7
9
7
30
2
7
9
25

예제 출력 1

5

예제 입력 2

8 50 4 7
2
7
9
25
7
9
7
30

예제 출력 2

4

Solution

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

int main(void)
{
	int N, d, k, c, *plate=NULL, *ate=NULL, max=0, count=0;

	scanf("%d%d%d%d", &N, &d, &k, &c);
	plate=(int *)malloc(N*sizeof(int));
	ate=(int *)calloc(d+1,sizeof(int));

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

	for(int i=0;i<k;i++)
		ate[plate[i]]++;
	ate[c]++;

	for(int i=1;i<=d;i++)
		if(ate[i]>0)
			count++;
	max=count;

	for(int i=1;i<N;i++)
	{
		if(ate[plate[i-1]]==1)
			count--;
		ate[plate[i-1]]--;
		if(ate[plate[(i+k-1)%N]]==0)
		{
			count++;
			if(count>max)
				max=count;
		}
		ate[plate[(i+k-1)%N]]++;
	}

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

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 7569번: 토마토 (0)	2023.02.19
<백준 알고리즘> 7576번: 토마토 (0)	2023.02.19
<백준 알고리즘> 2531번: 회전 초밥 (0)	2023.02.16
<백준 알고리즘> 2295번: 세 수의 합 (0)	2023.02.16
<백준 알고리즘> 17214번: 다항 함수의 적분 (0)	2023.02.16

문제

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.

원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.

위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.

회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다. 두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d 이하의 정수가 각 줄마다 하나씩 주어진다.

출력

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력한다.

예제 입력 1

8 30 4 30
7
9
7
30
2
7
9
25

예제 출력 1

5

예제 입력 2

8 50 4 7
2
7
9
25
7
9
7
30

예제 출력 2

4

Solution

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

int main(void)
{
	int N, d, k, c, *plate=NULL, *ate=NULL, max=0, count=0;

	scanf("%d%d%d%d", &N, &d, &k, &c);
	plate=(int *)malloc(N*sizeof(int));
	ate=(int *)calloc(d+1,sizeof(int));

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

	for(int i=0;i<k;i++)
		ate[plate[i]]++;
	ate[c]++;

	for(int i=1;i<=d;i++)
		if(ate[i]>0)
			count++;
	max=count;

	for(int i=1;i<N;i++)
	{
		if(ate[plate[i-1]]==1)
			count--;
		ate[plate[i-1]]--;
		if(ate[plate[(i+k-1)%N]]==0)
		{
			count++;
			if(count>max)
				max=count;
		}
		ate[plate[(i+k-1)%N]]++;
	}

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

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 7576번: 토마토 (0)	2023.02.19
<백준 알고리즘> 15961번: 회전 초밥 (0)	2023.02.16
<백준 알고리즘> 2295번: 세 수의 합 (0)	2023.02.16
<백준 알고리즘> 17214번: 다항 함수의 적분 (0)	2023.02.16
<백준 알고리즘> 16935번: 배열 돌리기 3 (0)	2023.02.16

문제

N(5 ≤ N ≤ 1,000)개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라.

예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다.

입력

첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에 차례로 U의 원소가 하나씩 주어진다. 주어진 U는 집합이 되므로 입력되는 두 수가 같아서는 안 된다. U의 원소는 200,000,000보다 작거나 같은 자연수이다. 답이 항상 존재하는 경우만 입력으로 주어진다.

출력

우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최대가 되도록 하는 것이 목적이다. x, y, z, k가 서로 같아도 된다. 이때, k번째 수를 출력하면 된다.

예제 입력 1

5
2
3
5
10
18

예제 출력 1

18

Solution

#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 main(void)
{
	int N, *U=NULL;

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

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

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

	for(int k=N-1;k>0;k--)
		for(int x=k-1;x>=0;x--)
		{
			int target=U[k]-U[x], left=0, right=x;

			while(left<right)
			{
				if(U[left]+U[right]<target)
					left++;
				else if(U[left]+U[right]>target)
					right--;
				else
					break;
			}

			if(U[left]+U[right]==target)
			{
				printf("%d\n", U[k]);
				free(U);
				return 0;
			}
		}

	free(U);
	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 15961번: 회전 초밥 (0)	2023.02.16
<백준 알고리즘> 2531번: 회전 초밥 (0)	2023.02.16
<백준 알고리즘> 17214번: 다항 함수의 적분 (0)	2023.02.16
<백준 알고리즘> 16935번: 배열 돌리기 3 (0)	2023.02.16
<백준 알고리즘> 1806번: 부분합 (0)	2023.02.15

문제

다항식(polynomial)은 문자의 거듭제곱의 상수 배들의 합을 표현하는 수식이다. 예를 들어 x^2+2x+3 같은 식을 의미한다. 그중 변수가 하나인 것을 일변수 다항식이라고 하고 이는 다음과 같이 표현한다.

f(x) = ax^n + bx^(n-1)+...+cx+d

최대 일차 일변수 다항식이 주어졌을 때 그 함수를 적분한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 최대 일차 일변수 다항식이 주어진다. 항의 개수는 최대 2개이고, 변수는 항상 x로 주어지며, 각 항은 공백 문자로 구분되지 않는다. 주어지는 계수는 절댓값이 10,000을 넘지 않는 0이 아닌 2의 배수이고 주어지는 상수는 절댓값이 10,000을 넘지 않는 정수이다. 차수가 같은 항은 한 번만 주어진다. 단, 계수의 절댓값이 1인 경우에는 1을 생략한다. 다항식은 차수가 큰 것부터 작아지는 순서대로 주어진다.

출력

주어진 일변수 다항식을 적분한 결과를 입력 형식과 동일하게 출력한다. 적분상수는 "W"로 x^2은 "xx"로 표현한다.

예제 입력 1

6x+6

예제 출력 1

3xx+6x+W

힌트

문제에서 다루는 적분법은

을 사용한다. (W는 적분상수) 또한 적분 가능 함수에 대하여 합의 법칙,

가 성립한다.

Solution

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

int main(void)
{
	char calculation[20]={'\0', };
	int variable=0, constant=0, index=0, minus[2]={1,1};

	fgets(calculation,sizeof(calculation),stdin);

	if(strlen(calculation)>1)
	{
		if(calculation[index]=='-')
		{
			minus[0]=-1;
			index++;
		}
		while(index<strlen(calculation) && calculation[index]!='x')
		{
			variable*=10;
			variable+=calculation[index++]-'0';
		}
		if(index<strlen(calculation) && calculation[index]=='x')
			index++;
		else
		{
			minus[1]=minus[0];
			minus[0]=1;
			variable-=calculation[index-1]-'0';
			variable/=10;
			constant=variable;
			variable=0;
		}
		if(index<strlen(calculation))
		{
			if(calculation[index]=='-')
				minus[1]=-1;
			index++;
		}
		while(index<strlen(calculation) && calculation[index]>='0' && calculation[index]<='9')
		{
			constant*=10;
			constant+=calculation[index++]-'0';
		}

		variable*=minus[0];
		switch(variable)
		{
			default:
				if(variable==-2)
					printf("-");
				else
					printf("%d", variable/2);
			case 2:
				printf("xx");
				if(minus[1]==1)
					printf("+");
			case 0:
				if(minus[1]==-1)
					printf("-");
				break;
		}
		switch(constant)
		{
			default:
				printf("%d", constant);
			case 1:
				printf("x+");
			case 0:
				break;
		}
	}
	printf("W\n");

	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 2531번: 회전 초밥 (0)	2023.02.16
<백준 알고리즘> 2295번: 세 수의 합 (0)	2023.02.16
<백준 알고리즘> 16935번: 배열 돌리기 3 (0)	2023.02.16
<백준 알고리즘> 1806번: 부분합 (0)	2023.02.15
<백준 알고리즘> 16927번: 배열 돌리기 2 (0)	2023.02.14

문제

크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다.

1번 연산은 배열을 상하 반전시키는 연산이다.

1 6 2 9 8 4 → 4 2 9 3 1 8
7 2 6 9 8 2 → 9 2 3 6 1 5
1 8 3 4 2 9 → 7 4 6 2 3 1
7 4 6 2 3 1 → 1 8 3 4 2 9
9 2 3 6 1 5 → 7 2 6 9 8 2
4 2 9 3 1 8 → 1 6 2 9 8 4
   <배열>       <연산 결과>

2번 연산은 배열을 좌우 반전시키는 연산이다.

1 6 2 9 8 4 → 4 8 9 2 6 1
7 2 6 9 8 2 → 2 8 9 6 2 7
1 8 3 4 2 9 → 9 2 4 3 8 1
7 4 6 2 3 1 → 1 3 2 6 4 7
9 2 3 6 1 5 → 5 1 6 3 2 9
4 2 9 3 1 8 → 8 1 3 9 2 4
   <배열>       <연산 결과>

3번 연산은 오른쪽으로 90도 회전시키는 연산이다.

1 6 2 9 8 4 → 4 9 7 1 7 1
7 2 6 9 8 2 → 2 2 4 8 2 6
1 8 3 4 2 9 → 9 3 6 3 6 2
7 4 6 2 3 1 → 3 6 2 4 9 9
9 2 3 6 1 5 → 1 1 3 2 8 8
4 2 9 3 1 8 → 8 5 1 9 2 4
   <배열>       <연산 결과>

4번 연산은 왼쪽으로 90도 회전시키는 연산이다.

1 6 2 9 8 4 → 4 2 9 1 5 8
7 2 6 9 8 2 → 8 8 2 3 1 1
1 8 3 4 2 9 → 9 9 4 2 6 3
7 4 6 2 3 1 → 2 6 3 6 3 9
9 2 3 6 1 5 → 6 2 8 4 2 2
4 2 9 3 1 8 → 1 7 1 7 9 4
   <배열>       <연산 결과>

5, 6번 연산을 수행하려면 배열을 크기가 N/2×M/2인 4개의 부분 배열로 나눠야 한다. 아래 그림은 크기가 6×8인 배열을 4개의 그룹으로 나눈 것이고, 1부터 4까지의 수로 나타냈다.

1 1 1 1 2 2 2 2
1 1 1 1 2 2 2 2
1 1 1 1 2 2 2 2
4 4 4 4 3 3 3 3
4 4 4 4 3 3 3 3
4 4 4 4 3 3 3 3

5번 연산은 1번 그룹의 부분 배열을 2번 그룹 위치로, 2번을 3번으로, 3번을 4번으로, 4번을 1번으로 이동시키는 연산이다.

3 2 6 3 1 2 9 7 → 2 1 3 8 3 2 6 3
9 7 8 2 1 4 5 3 → 1 3 2 8 9 7 8 2
5 9 2 1 9 6 1 8 → 4 5 1 9 5 9 2 1
2 1 3 8 6 3 9 2 → 6 3 9 2 1 2 9 7
1 3 2 8 7 9 2 1 → 7 9 2 1 1 4 5 3
4 5 1 9 8 2 1 3 → 8 2 1 3 9 6 1 8
     <배열>            <연산 결과>

6번 연산은 1번 그룹의 부분 배열을 4번 그룹 위치로, 4번을 3번으로, 3번을 2번으로, 2번을 1번으로 이동시키는 연산이다.

3 2 6 3 1 2 9 7 → 1 2 9 7 6 3 9 2
9 7 8 2 1 4 5 3 → 1 4 5 3 7 9 2 1
5 9 2 1 9 6 1 8 → 9 6 1 8 8 2 1 3
2 1 3 8 6 3 9 2 → 3 2 6 3 2 1 3 8
1 3 2 8 7 9 2 1 → 9 7 8 2 1 3 2 8
4 5 1 9 8 2 1 3 → 5 9 2 1 4 5 1 9
     <배열>            <연산 결과>

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 연산의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 A[i][j]가 주어진다.

마지막 줄에는 수행해야 하는 연산이 주어진다. 연산은 공백으로 구분되어져 있고, 문제에서 설명한 연산 번호이며, 순서대로 적용시켜야 한다.

출력

입력으로 주어진 배열에 R개의 연산을 순서대로 수행한 결과를 출력한다.

제한

2 ≤ N, M ≤ 100
1 ≤ R ≤ 1,000
N, M은 짝수
1 ≤ A[i][j] ≤ 10^8

예제 입력 1

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

예제 출력 1

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

예제 입력 2

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

예제 출력 2

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

예제 입력 3

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

예제 출력 3

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

예제 입력 4

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

예제 출력 4

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

예제 입력 5

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

예제 출력 5

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

예제 입력 6

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

예제 출력 6

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

예제 입력 7

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

예제 출력 7

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

Solution

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

int main(void)
{
	int N, M, ***A=NULL, R, *order=NULL, bigger, current=0;

	scanf("%d%d%d", &N, &M, &R);
	bigger=N>M?N:M;
	A=(int ***)malloc(2*sizeof(int **));
	for(int i=0;i<2;i++)
	{
		A[i]=(int **)malloc(bigger*sizeof(int *));
		for(int j=0;j<bigger;j++)
			A[i][j]=(int *)malloc(bigger*sizeof(int));
	}
	order=(int *)malloc(R*sizeof(int));

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

	for(int r=0;r<R;r++)
		switch(order[r])
		{
			case 1:
			case 2:
				int one=0, two=0;
				while(r<R && order[r]>=1 && order[r]<=2)
				{
					if(order[r]==1)
						one++;
					else
						two++;
					r++;
				}
				r--;
				one%=2;
				two%=2;
				if(one==1)
				{
					int now=current%2, next=(current+1)%2;
					for(int n=0;n<N;n++)
						for(int m=0;m<M;m++)
							A[next][N-n-1][m]=A[now][n][m];
					current++;
				}
				if(two==1)
				{
					int now=current%2, next=(current+1)%2;
					for(int n=0;n<N;n++)
						for(int m=0;m<M;m++)
							A[next][n][m]=A[now][n][M-m-1];
					current++;
				}
				break;
			case 3:
			case 4:
				int right=0;

				while(r<R && order[r]>=3 && order[r]<=4)
				{
					if(order[r]==3)
						right++;
					else
						right--;
					r++;
				}
				r--;

				if(right<0)
				{
					while(right<-3)
						right+=4;
					while(right<0)
					{
						int now=current%2, next=(current+1)%2;
						right++;
						for(int m=0;m<M;m++)
							for(int n=0;n<N;n++)
								A[next][m][n]=A[now][n][M-m-1];
						current++;
						int temp=M;
						M=N;
						N=temp;
					}
				}
				else
				{
					right%=4;
					while(right>0)
					{
						int now=current%2, next=(current+1)%2;
						right--;
						for(int m=0;m<M;m++)
							for(int n=0;n<N;n++)
								A[next][m][n]=A[now][N-n-1][m];
						current++;
						int temp=M;
						M=N;
						N=temp;
					}
				}
				break;
			case 5:
			case 6:
				int clock=0;

				while(r<R && order[r]>=5 && order[r]<=6)
				{
					if(order[r]==5)
						clock++;
					else
						clock--;
					r++;
				}
				r--;

				while(clock<0)
					clock+=4;
				clock%=4;

				int now=current%2, next=(current+1)%2;
				switch(clock)
				{
					case 0:
						break;
					case 1:
						for(int n=0;n<N/2;n++)
							for(int m=0;m<M/2;m++)
								A[next][n][m]=A[now][n+N/2][m];
						for(int n=0;n<N/2;n++)
							for(int m=0;m<M/2;m++)
								A[next][n+N/2][m]=A[now][n+N/2][m+M/2];
						for(int n=0;n<N/2;n++)
							for(int m=0;m<M/2;m++)
								A[next][n+N/2][m+M/2]=A[now][n][m+M/2];
						for(int n=0;n<N/2;n++)
							for(int m=0;m<M/2;m++)
								A[next][n][m+M/2]=A[now][n][m];
						current++;
						break;
					case 2:
						for(int i=0;i<2;i++)
						{
							for(int n=0;n<N/2;n++)
								for(int m=0;m<M/2;m++)
									A[next][n+N/2][m]=A[now][n][m];
							for(int n=0;n<N/2;n++)
								for(int m=0;m<M/2;m++)
									A[next][n+N/2][m+M/2]=A[now][n+N/2][m];
							for(int n=0;n<N/2;n++)
								for(int m=0;m<M/2;m++)
									A[next][n][m+M/2]=A[now][n+N/2][m+M/2];
							for(int n=0;n<N/2;n++)
								for(int m=0;m<M/2;m++)
									A[next][n][m]=A[now][n][m+M/2];
							current++;
							now^=1;
							next^=1;
						}
						break;
					case 3:
						for(int n=0;n<N/2;n++)
							for(int m=0;m<M/2;m++)
								A[next][n+N/2][m]=A[now][n][m];
						for(int n=0;n<N/2;n++)
							for(int m=0;m<M/2;m++)
								A[next][n+N/2][m+M/2]=A[now][n+N/2][m];
						for(int n=0;n<N/2;n++)
							for(int m=0;m<M/2;m++)
								A[next][n][m+M/2]=A[now][n+N/2][m+M/2];
						for(int n=0;n<N/2;n++)
							for(int m=0;m<M/2;m++)
								A[next][n][m]=A[now][n][m+M/2];
						current++;
						break;
				}
				break;
		}

		current%=2;
		for(int n=0;n<N;n++)
		{
			for(int m=0;m<M;m++)
				printf("%d ", A[current][n][m]);
			printf("\n");
		}

		free(order);
		for(int i=0;i<2;i++)
		{
			for(int j=0;j<bigger;j++)
				free(A[i][j]);
			free(A[i]);
		}
		free(A);
		return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 2295번: 세 수의 합 (0)	2023.02.16
<백준 알고리즘> 17214번: 다항 함수의 적분 (0)	2023.02.16
<백준 알고리즘> 1806번: 부분합 (0)	2023.02.15
<백준 알고리즘> 16927번: 배열 돌리기 2 (0)	2023.02.14
<백준 알고리즘> 1068번: 트리 (0)	2023.02.14