'분류 전체보기' 카테고리의 글 목록 (3 Page)

문제

크기가 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

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력 1

2

Solution

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

int main(void)
{
	int N, S, min=100000, *arr=NULL, left=0, right=0;

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

	for(int n=1;n<=N;n++)
	{
		scanf("%d", &arr[n]);
		arr[n]+=arr[n-1];
	}

	if(arr[N]<S)
	{
		printf("0\n");
		return 0;
	}

	while(right<N && arr[++right]<S);
	while(left<right && arr[right]-arr[++left]>=S);
	min=right-left<min?right-left:min;
	while(++right<=N)
	{
		while(left<right && arr[right]-arr[++left]>=S);
		min=right-left<min?right-left:min;
	}

	printf("%d\n", min+1);
	free(arr);
	return 0;
}

728x90

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

<백준 알고리즘> 17214번: 다항 함수의 적분 (0)	2023.02.16
<백준 알고리즘> 16935번: 배열 돌리기 3 (0)	2023.02.16
<백준 알고리즘> 16927번: 배열 돌리기 2 (0)	2023.02.14
<백준 알고리즘> 1068번: 트리 (0)	2023.02.14
<백준 알고리즘> 1715번: 카드 정렬하기 (0)	2023.02.14

입력

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

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

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

2 ≤ N, M ≤ 300
1 ≤ R ≤ 10^9
min(N, M) mod 2 = 0
1 ≤ A[i][j] ≤ 10^8

예제 입력 1

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

예제 출력 1

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

예제 입력 2

5 4 7
1 2 3 4
7 8 9 10
13 14 15 16
19 20 21 22
25 26 27 28

예제 출력 2

28 27 26 25
22 9 15 19
16 8 21 13
10 14 20 7
4 3 2 1

예제 입력 3

2 2 3
1 1
1 1

예제 출력 3

1 1
1 1

Solution

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

int main(void)
{
	int N, M, R, **A=NULL, NS=0, MS=0, NE, ME;

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

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

	NE=N-1;
	ME=M-1;

	while(NS<NE && MS<ME)
	{
		int rotate=R%(2*(NE-NS+ME-MS));

		for(int r=0;r<rotate;r++)
		{
			int temp=A[NS][MS];

			for(int m=MS;m<ME;m++)
				A[NS][m]=A[NS][m+1];
			for(int n=NS;n<NE;n++)
				A[n][ME]=A[n+1][ME];
			for(int m=ME;m>MS;m--)
				A[NE][m]=A[NE][m-1];
			for(int n=NE;n>NS;n--)
				A[n][MS]=A[n-1][MS];
			A[NS+1][MS]=temp;
		}
		NS++;
		NE--;
		MS++;
		ME--;
	}

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

728x90

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

<백준 알고리즘> 16935번: 배열 돌리기 3 (0)	2023.02.16
<백준 알고리즘> 1806번: 부분합 (0)	2023.02.15
<백준 알고리즘> 1068번: 트리 (0)	2023.02.14
<백준 알고리즘> 1715번: 카드 정렬하기 (0)	2023.02.14
<백준 알고리즘> 1987번: 알파벳 (0)	2023.02.14

문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

이제 리프 노드의 개수는 1개이다.

입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

예제 입력 1

5
-1 0 0 1 1
2

예제 출력 1

2

예제 입력 2

5
-1 0 0 1 1
1

예제 출력 2

1

예제 입력 3

5
-1 0 0 1 1
0

예제 출력 3

0

예제 입력 4

9
-1 0 0 2 2 4 4 6 6
4

예제 출력 4

2

Solution

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

int main(void)
{
	int N, *parent=NULL, **child=NULL, *child_count=NULL, del, *queue=NULL, front=0, rear=0, count=0;

	scanf("%d", &N);
	parent=(int *)malloc(N*sizeof(int));
	child_count=(int *)calloc(N,sizeof(int));
	child=(int **)malloc(N*sizeof(int *));
	queue=(int *)malloc(N*sizeof(int));

	for(int n=0;n<N;n++)
	{
		scanf("%d", &parent[n]);
		if(parent[n]!=-1)
			child_count[parent[n]]++;
	}

	for(int n=0;n<N;n++)
		child[n]=(int *)malloc(child_count[n]*sizeof(int));

	free(child_count);
	child_count=(int *)calloc(N,sizeof(int));

	for(int n=0;n<N;n++)
		if(parent[n]!=-1)
			child[parent[n]][child_count[parent[n]]++]=n;

	scanf("%d", &del);
	if(parent[del]>=0)
		child_count[parent[del]]--;
	queue[rear++]=del;

	while(front<rear)
	{
		for(int i=0;i<child_count[queue[front]];i++)
			queue[rear++]=child[queue[front]][i];
		child_count[queue[front++]]=-1;
	}

	for(int n=0;n<N;n++)
		count+=child_count[n]==0;

	printf("%d\n", count);
	free(child_count);
	for(int n=0;n<N;n++)
		free(child[n]);
	free(queue);
	free(child);
	free(parent);
	return 0;
}

728x90

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

<백준 알고리즘> 1806번: 부분합 (0)	2023.02.15
<백준 알고리즘> 16927번: 배열 돌리기 2 (0)	2023.02.14
<백준 알고리즘> 1715번: 카드 정렬하기 (0)	2023.02.14
<백준 알고리즘> 1987번: 알파벳 (0)	2023.02.14
<백준 알고리즘> 1406번: 에디터 (0)	2023.02.14

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

예제 입력 1

3
10
20
40

예제 출력 1

100

Solution

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

int main(void)
{
	int *card=(int *)calloc(1001,sizeof(int)), N, num, pri=1, sec, sum=0;
	long long count=0;

	scanf("%d", &N);
	for(int n=0;n<N;n++)
	{
		scanf("%d", &num);
		card[num]++;
		sum+=num;
	}

	card=realloc(card,(sum+1)*sizeof(int));
	for(int n=1;n<N;n++)
	{
		while(card[pri]==0)
			pri++;

		sec=pri;
		if(card[pri]==1)
		{
			sec++;
			while(card[sec]==0)
				sec++;
		}

		count+=pri+sec;
		card[pri+sec]++;
		card[pri]--;
		card[sec]--;

		pri=sec;
	}

	printf("%lld\n", count);
	free(card);
	return 0;
}

728x90

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

<백준 알고리즘> 16927번: 배열 돌리기 2 (0)	2023.02.14
<백준 알고리즘> 1068번: 트리 (0)	2023.02.14
<백준 알고리즘> 1987번: 알파벳 (0)	2023.02.14
<백준 알고리즘> 1406번: 에디터 (0)	2023.02.14
<백준 알고리즘> 16926번: 배열 돌리기 1 (0)	2023.02.14

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력 1

2 4
CAAB
ADCB

예제 출력 1

3

예제 입력 2

3 6
HFDFFB
AJHGDH
DGAGEH

예제 출력 2

6

예제 입력 3

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

예제 출력 3

10

Solution

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

char **board=NULL;
int R, C;

int max_move(int x,int y,int bit)
{
	int move[4]={0, }, max=0;

	for(int i=0;i<26;i++)
		if(bit&1<<i)
			max++;

	if(x>0 && (bit&(1<<(board[x-1][y]-'A')))==0)
		move[0]=max_move(x-1,y,bit|1<<(board[x-1][y]-'A'));
	if(x<R-1 && (bit&(1<<(board[x+1][y]-'A')))==0)
		move[1]=max_move(x+1,y,bit|1<<(board[x+1][y]-'A'));
	if(y>0 && (bit&(1<<(board[x][y-1]-'A')))==0)
		move[2]=max_move(x,y-1,bit|1<<(board[x][y-1]-'A'));
	if(y<C-1 && (bit&(1<<(board[x][y+1]-'A')))==0)
		move[3]=max_move(x,y+1,bit|1<<(board[x][y+1]-'A'));

	for(int i=0;i<4;i++)
		if(move[i]>max)
			max=move[i];

	return max;
}
int main(void)
{
	scanf("%d%d", &R, &C);
	board=(char **)malloc(R*sizeof(char *));
	for(int r=0;r<R;r++)
	{
		getchar();
		board[r]=(char *)calloc(C+1,sizeof(char));

		for(int c=0;c<C;c++)
			scanf("%c", &board[r][c]);
	}

	printf("%d\n", max_move(0,0,1<<(board[0][0]-'A')));
	for(int r=0;r<R;r++)
		free(board[r]);
	free(board);
	return 0;
}

Solution

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static String[] board;
	static int R, C;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		R=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		board=new String[R];
		
		for(int i=0;i<R;i++)
			board[i]=br.readLine();
		
		System.out.println(maxMove(0,1<<board[0].charAt(0)-'A'));
	}
	
	static int maxMove(int index,int bit) {
		int[] move=new int[4];
		int x=index/100, y=index%100, max=0;
		
		for(int i=0;i<26;i++)
			if((bit&1<<i)!=0)
				max++;
		
		if(x>0 && (bit&(1<<board[x-1].charAt(y)-'A'))==0)
			move[0]=maxMove(100*(x-1)+y,bit|1<<(board[x-1].charAt(y)-'A'));
		if(x<R-1 && (bit&(1<<board[x+1].charAt(y)-'A'))==0)
			move[1]=maxMove(100*(x+1)+y,bit|1<<(board[x+1].charAt(y)-'A'));
		if(y>0 && (bit&(1<<board[x].charAt(y-1)-'A'))==0)
			move[2]=maxMove(100*(x)+y-1,bit|1<<(board[x].charAt(y-1)-'A'));
		if(y<C-1 && (bit&(1<<board[x].charAt(y+1)-'A'))==0)
			move[3]=maxMove(100*(x)+y+1,bit|1<<(board[x].charAt(y+1)-'A'));
		
		for(int i=0;i<4;i++)
			max=Integer.max(max, move[i]);

		return max;
	}
}

728x90

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

<백준 알고리즘> 1068번: 트리 (0)	2023.02.14
<백준 알고리즘> 1715번: 카드 정렬하기 (0)	2023.02.14
<백준 알고리즘> 1406번: 에디터 (0)	2023.02.14
<백준 알고리즘> 16926번: 배열 돌리기 1 (0)	2023.02.14
<백준 알고리즘> 11025번: 요세푸스 문제 3 (0)	2023.02.13

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $	$라는 문자를 커서 왼쪽에 추가함

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

예제 입력 1

abcd
3
P x
L
P y

예제 출력 1

abcdyx

예제 입력 2

abc
9
L
L
L
L
L
P x
L
B
P y

예제 출력 2

yxabc

예제 입력 3

dmih
11
B
B
P x
L
B
B
B
P y
D
D
P z

예제 출력 3

yxz

Solution

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

typedef struct ListNode
{
	char value;
	struct ListNode *prev;
	struct ListNode *next;
}
ListNode;

ListNode *root=NULL;

ListNode *create_node(char value,ListNode *prev)
{
	ListNode *new_node=(ListNode *)malloc(sizeof(ListNode));

	prev->next=new_node;
	new_node->value=value;
	new_node->prev=prev;
	new_node->next=NULL;

	return new_node;
}

ListNode *delete_node(ListNode *del)
{
	if(del==root)
		return root;

	ListNode *temp=del->prev;

	temp->next=del->next;
	if(del->next!=NULL)
		del->next->prev=temp;

	free(del);
	return temp;
}

ListNode *insert_node(ListNode *current,char value)
{
	ListNode *insert=(ListNode *)malloc(sizeof(ListNode));

	insert->value=value;
	insert->prev=current;
	insert->next=current->next;
	current->next=insert;
	if(insert->next!=NULL)
		insert->next->prev=insert;

	return insert;
}

ListNode *left(ListNode *current)
{
	return current==root?current:current->prev;
}

ListNode *right(ListNode *current)
{
	return current->next==NULL?current:current->next;
}

void print_root()
{
	root=root->next;

	while(root!=NULL)
	{
		printf("%c", root->value);
		root=root->next;
	}
}

int main(void)
{
	char str[100001]={'\0', }, command, value;
	ListNode *current=NULL;
	int N, len;

	scanf("%s", str);
	len=strlen(str);

	root=(ListNode *)malloc(sizeof(ListNode));
	root->value='\0';
	current=create_node(str[0],root);
	for(int i=1;i<len;i++)
		current=create_node(str[i],current);

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

	for(int n=0;n<N;n++)
	{
		scanf("%c", &command);

		switch(command)
		{
			case 'L':
				current=left(current);
				break;
			case 'D':
				current=right(current);
				break;
			case 'B':
				current=delete_node(current);
				break;
			case 'P':
				getchar();
				scanf("%c", &value);
				current=insert_node(current,value);
				break;
		}
		getchar();
	}

	print_root();
	return 0;
}

Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static class ListNode {
		char value;
		ListNode prev;
		ListNode next;
		
		public ListNode() {
			this.value='\0';
			this.prev=null;
			this.next=null;
		}
		
		public ListNode(char value,ListNode current) {
			this.value=value;
			this.prev=current;
			this.next=null;
		}
		
		static ListNode createNode(char value,ListNode prev) {
			ListNode newNode=new ListNode(value,prev);
			newNode.prev.next=newNode;
			return newNode;
		}
		
		ListNode deleteNode(ListNode del) {
			if(del.equals(root))
				return root;

			ListNode temp=del.prev;
			temp.next=del.next;
			if(del.next!=null)
				del.next.prev=temp;
			
			return temp;
		}
		
		ListNode insertNode(char value,ListNode current) {
			ListNode insert=new ListNode(value,current);
			
			insert.next=current.next;
			current.next=insert;
			
			if(insert.next!=null)
				insert.next.prev=insert;
			
			return insert;
		}
		
		ListNode left(ListNode current) {
			return current.equals(root)?current:current.prev;
		}
		
		ListNode right(ListNode current) {
			return current.next==null?current:current.next;
		}
	}
	
	public static ListNode root;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb=new StringBuilder();
		String str=br.readLine();
		
		root=new ListNode();
		ListNode current=ListNode.createNode(str.charAt(0),root);
		for(int i=1;i<str.length();i++)
			current=ListNode.createNode(str.charAt(i),current);

		int N=Integer.parseInt(br.readLine());
		for(int n=0;n<N;n++) {
			st=new StringTokenizer(br.readLine());
			switch(st.nextToken().charAt(0)) {
			case 'L':
				current=current.left(current);
				break;
			case 'D':
				current=current.right(current);
				break;
			case 'B':
				current=current.deleteNode(current);
				break;
			case 'P':
				current=current.insertNode(st.nextToken().charAt(0), current);
				break;
			}
		}
		
		root=root.next;
		while(root!=null) {
			sb.append(root.value);
			root=root.next;
		}
		System.out.println(sb.toString());
	}
}

728x90

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

<백준 알고리즘> 1715번: 카드 정렬하기 (0)	2023.02.14
<백준 알고리즘> 1987번: 알파벳 (0)	2023.02.14
<백준 알고리즘> 16926번: 배열 돌리기 1 (0)	2023.02.14
<백준 알고리즘> 11025번: 요세푸스 문제 3 (0)	2023.02.13
<백준 알고리즘> 1789번: 수들의 합 (0)	2023.02.13

문제

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
   ↓                                       ↑
A[2][1]   A[2][2] ← A[2][3] ← A[2][4]   A[2][5]
   ↓         ↓                   ↑         ↑
A[3][1]   A[3][2] → A[3][3] → A[3][4]   A[3][5]
   ↓                                       ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

1 2 3 4       2 3 4 8       3 4 8 6
5 6 7 8       1 7 7 6       2 7 8 2
9 8 7 6   →   5 6 8 2   →   1 7 6 3
5 4 3 2       9 5 4 3       5 9 5 4
 <시작>         <회전1>        <회전2>

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

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

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

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

2 ≤ N, M ≤ 300
1 ≤ R ≤ 1,000
min(N, M) mod 2 = 0
1 ≤ A[i][j] ≤ 10^8

예제 입력 1

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

예제 출력 1

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

예제 입력 2

5 4 7
1 2 3 4
7 8 9 10
13 14 15 16
19 20 21 22
25 26 27 28

예제 출력 2

28 27 26 25
22 9 15 19
16 8 21 13
10 14 20 7
4 3 2 1

예제 입력 3

2 2 3
1 1
1 1

예제 출력 3

1 1
1 1

Solution

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

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

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

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

	for(int r=0;r<R;r++)
	{
		int NS=0, MS=0, NE=N-1, ME=M-1;

		while(NS<NE && MS<ME)
		{
			int temp=A[NS][MS];

			for(int m=MS;m<ME;m++)
				A[NS][m]=A[NS][m+1];
			for(int n=NS;n<NE;n++)
				A[n][ME]=A[n+1][ME];
			for(int m=ME;m>MS;m--)
				A[NE][m]=A[NE][m-1];
			for(int n=NE;n>NS;n--)
				A[n][MS]=A[n-1][MS];
			A[NS+1][MS]=temp;
				NE--;
				NS++;
				ME--;
				MS++;
		}
	}

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

Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb=new StringBuilder();
		
		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		int R=Integer.parseInt(st.nextToken());
		int[][] A=new int[N][M];

		for(int n=0;n<N;n++) {
			st=new StringTokenizer(br.readLine());
			for(int m=0;m<M;m++)
				A[n][m]=Integer.parseInt(st.nextToken());
		}
		
		for(int r=0;r<R;r++) {
			int NS=0, MS=0, NE=N-1, ME=M-1;
			
			while(NS<NE && MS<ME) {
				int temp=A[NS][MS];
			
				for(int m=MS;m<ME;m++)
					A[NS][m]=A[NS][m+1];
				for(int n=NS;n<NE;n++)
					A[n][ME]=A[n+1][ME];
				for(int m=ME;m>MS;m--)
					A[NE][m]=A[NE][m-1];
				for(int n=NE;n>NS;n--)
					A[n][MS]=A[n-1][MS];
				A[NS+1][MS]=temp;
					NE--;
					NS++;
					ME--;
					MS++;
			}
		}
		
		for(int n=0;n<N;n++) {
			for(int m=0;m<M;m++)
				sb.append(A[n][m]+" ");
			sb.append("\n");
		}
		
		System.out.print(sb.toString());
	}
}

728x90

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

<백준 알고리즘> 1987번: 알파벳 (0)	2023.02.14
<백준 알고리즘> 1406번: 에디터 (0)	2023.02.14
<백준 알고리즘> 11025번: 요세푸스 문제 3 (0)	2023.02.13
<백준 알고리즘> 1789번: 수들의 합 (0)	2023.02.13
<백준 알고리즘> 17406번: 배열 돌리기 4 (0)	2023.02.13