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

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 P(N)이라고 한다.

P(1) IOI
P(2) IOIOI
P(3) IOIOIOI
P(N) IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 P(N)이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

S에 P(N)이 몇 군데 포함되어 있는지 출력한다.

제한

1 ≤ N ≤ 1,000,000
2N+1 ≤ M ≤ 1,000,000
S는 I와 O로만 이루어져 있다.

서브태스크

번호	배점	제한
1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

예제 입력 1

1
13
OOIOIOIOIIOII

예제 출력 1

4

OOIOIOIOIIOII
OOIOIOIOIIOII
OOIOIOIOIIOII
OOIOIOIOIIOII

예제 입력 2

2
13
OOIOIOIOIIOII

예제 출력 2

2

OOIOIOIOIIOII
OOIOIOIOIIOII

Solution

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

int main(void)
{
	int N, M, len=0, count=0;
	char *S=NULL;

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

	scanf("%s", S);

	for(int i=2;i<M;i++)
		if(S[i]=='I')
		{
			if(S[i-1]=='O' && S[i-2]=='I')
			{
				len++;
				if(len>=N)
					count++;
			}
			else
				len=0;
		}

	printf("%d\n", count);
	free(S);
	return 0;
}

728x90

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

<백준 알고리즘> 11403번: 경로 찾기 (0)	2023.01.25
<백준 알고리즘> 15686번: 치킨 배달 (0)	2023.01.25
<백준 알고리즘> 1107번: 리모컨 (1)	2023.01.22
<백준 알고리즘> 18111번: 마인크래프트 (1)	2023.01.22
<백준 알고리즘> 15829번: Hashing (0)	2023.01.22

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

예제 입력 1

5457
3
6 7 8

예제 출력 1

6

예제 입력 2

100
5
0 1 2 3 4

예제 출력 2

0

예제 입력 3

500000
8
0 2 3 4 6 7 8 9

예제 출력 3

11117

예제 입력 4

100
3
1 0 5

예제 출력 4

0

예제 입력 5

14124
0

예제 출력 5

5

예제 입력 6

1
9
1 2 3 4 5 6 7 8 9

예제 출력 6

2

예제 입력 7

80000
2
8 9

예제 출력 7

2228

Solution

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

int abs(int N)
{
	return N>0?N:-N;
}

int main(void)
{
	int N, M, num, hundred, best=999999999, count=0;
	bool normal[10];

	for(int i=0;i<10;i++)
		normal[i]=true;

	scanf("%d", &N);
	scanf("%d", &M);
	for(int m=0;m<M;m++)
	{
		scanf("%d", &num);
		normal[num]=false;
	}

	hundred=abs(N-100);

	if(hundred<2 || M==10)
	{
		printf("%d\n", hundred);
		return 0;
	}

	for(int n=0;n<1000000;n++)
	{
		bool able=true;
		count=0;
		num=n;

		if(num==0)
			for(int i=0;i<10;i++)
				if(normal[i])
				{
					count=i+1;
					break;
				}
		while(num>0)
		{
			if(!normal[num%10])
			{
				able=false;
				break;
			}
			count++;
			num/=10;
		}

		if(able)
			best=count+abs(N-n)>best?best:count+abs(N-n);
	}

	printf("%d\n", best>hundred?hundred:best);
	return 0;
}

728x90

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

<백준 알고리즘> 15686번: 치킨 배달 (0)	2023.01.25
<백준 알고리즘> 5525번: IOIOI (0)	2023.01.22
<백준 알고리즘> 18111번: 마인크래프트 (1)	2023.01.22
<백준 알고리즘> 15829번: Hashing (0)	2023.01.22
<백준 알고리즘> 11660번: 구간 합 구하기 5 (0)	2023.01.22

문제

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.

목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.

lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.

좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.

1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다. 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

입력

첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 10^7)

둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다. (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다. 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 땅을 고르는 데 걸리는 시간과 땅의 높이를 출력하시오. 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.

예제 입력 1

3 4 99
0 0 0 0
0 0 0 0
0 0 0 1

예제 출력 1

2 0

예제 입력 2

3 4 1
64 64 64 64
64 64 64 64
64 64 64 63

예제 출력 2

1 64

인벤토리에 블록이 하나 있기 때문에, 맨 오른쪽 아래에 블록을 하나 채우면 된다.

예제 입력 3

3 4 0
64 64 64 64
64 64 64 64
64 64 64 63

예제 출력 3

22 63

Solution

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

int main(void)
{
	int N, M, B, **land=NULL, min=256, max=0, best=2100000000, best_height;

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

	for(int i=0;i<N;i++)
		for(int j=0;j<M;j++)
		{
			scanf("%d", &land[i][j]);
			if(land[i][j]>max)
				max=land[i][j];
			if(land[i][j]<min)
				min=land[i][j];
		}

	for(int count=min;count<=max;count++)
	{
		int sec=0, left=B;
		bool able=true;

		for(int i=0;i<N;i++)
			for(int j=0;j<M;j++)
				if(land[i][j]>count)
				{
					sec+=2*(land[i][j]-count);
					left+=land[i][j]-count;
				}

		for(int i=0;i<N;i++)
		{
			for(int j=0;j<M;j++)				
				if(land[i][j]<count)
				{
					sec+=count-land[i][j];
					if(count-land[i][j]>left)
					{
						able=false;
						break;
					}
					left-=count-land[i][j];
				}
			if(!able)
				break;
		}

		if(able && sec<=best)
		{
			best=sec;
			best_height=count;
		}
	}

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

728x90

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

<백준 알고리즘> 5525번: IOIOI (0)	2023.01.22
<백준 알고리즘> 1107번: 리모컨 (1)	2023.01.22
<백준 알고리즘> 15829번: Hashing (0)	2023.01.22
<백준 알고리즘> 11660번: 구간 합 구하기 5 (0)	2023.01.22
<백준 알고리즘> 11659번: 구간 합 구하기 4 (0)	2023.01.21

문제

APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.

이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은 수열 1, 2, 2, 1로 나타낼 수 있다.

해시 값을 계산하기 위해서 우리는 문자열 혹은 수열을 하나의 정수로 치환하려고 한다. 간단하게는 수열의 값을 모두 더할 수도 있다. 해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 M으로 나눠주자. 짜잔! 해시 함수가 완성되었다. 이를 수식으로 표현하면 아래와 같다.

해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져있다. 다들 비둘기 집의 원리에 대해서는 한 번쯤 들어봤을 것이다. 그 원리에 의하면 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다. 이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다. 위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니까 조금 더 개선해보자.

어떻게 하면 순서가 달라졌을때 출력값도 달라지게 할 수 있을까? 머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다. 가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다. 이를 수식으로 표현하면 아래와 같다.

보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다. 우리가 직접 정하라고 하면 힘들테니까 r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891(놀랍게도 소수이다!!)로 하자.

이제 여러분이 할 일은 위 식을 통해 주어진 문자열의 해시 값을 계산하는 것이다. 그리고 이 함수는 간단해 보여도 자주 쓰이니까 기억해뒀다가 잘 써먹도록 하자.

입력

첫 줄에는 문자열의 길이 L이 들어온다. 둘째 줄에는 영문 소문자로만 이루어진 문자열이 들어온다.

입력으로 주어지는 문자열은 모두 알파벳 소문자로만 구성되어 있다.

출력

문제에서 주어진 해시함수와 입력으로 주어진 문자열을 사용해 계산한 해시 값을 정수로 출력한다.

Small (50점)

1 ≤ L ≤ 5

Large (50점)

1 ≤ L ≤ 50

예제 입력 1

5
abcde

예제 출력 1

4739715

예제 입력 2

3
zzz

예제 출력 2

25818

예제 입력 3

1
i

예제 출력 3

9

힌트

예제 1: abcde의 해시 값은 1 × 310 + 2 × 311 + 3 × 312 + 4 × 313 + 5 × 314 = 1 + 62 + 2883 + 119164 + 4617605 = 4739715이다.

예제 2: zzz의 해시 값은 26 × 310 + 26 × 311 + 26 × 312 = 26 + 806 + 24986 = 25818이다.

Solution

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

int main(void)
{
	long long L, num, hash=0, mul=1;
	char *str=NULL;

	scanf("%lld", &L);
	str=(char *)calloc(L,sizeof(char));
	scanf("%s", str);

	for(long long i=0;i<L;i++)
	{
		num=str[i]-'a'+1;

		num=mul*num;
		num%=1234567891;

		hash+=num;
		hash%=1234567891;

		mul*=31;
		mul%=1234567891;
	}

	printf("%lld\n", hash);
	free(str);
	return 0;
}

728x90

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

<백준 알고리즘> 1107번: 리모컨 (1)	2023.01.22
<백준 알고리즘> 18111번: 마인크래프트 (1)	2023.01.22
<백준 알고리즘> 11660번: 구간 합 구하기 5 (0)	2023.01.22
<백준 알고리즘> 11659번: 구간 합 구하기 4 (0)	2023.01.21
<백준 알고리즘> 4949번: 균형잡힌 세상 (0)	2023.01.21

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

예제 입력 1

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

예제 출력 1

27
6
64

예제 입력 2

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

예제 출력 2

1
2
3
4

Solution

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

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

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

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

	for(int m=0;m<M;m++)
	{
		int x1, x2, y1, y2;

		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		printf("%d\n", accumulate[x2][y2]-accumulate[x2][y1-1]-accumulate[x1-1][y2]+accumulate[x1-1][y1-1]);
	}

	for(int n=0;n<=N;n++)
	{
		free(arr[n]);
		free(accumulate[n]);
	}
	free(arr);
	free(accumulate);
	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 IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		int[][] arr=new int[N+1][N+1];
		int[][] accumulate=new int[N+1][N+1];
		int x1, x2, y1, y2;
		
		for(int i=1;i<=N;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=1;j<=N;j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());
				accumulate[i][j]=arr[i][j]+accumulate[i-1][j]+accumulate[i][j-1]-accumulate[i-1][j-1];
			}
		}
		
		for(int m=0;m<M;m++) {
			st=new StringTokenizer(br.readLine());
			x1=Integer.parseInt(st.nextToken());
			y1=Integer.parseInt(st.nextToken());
			x2=Integer.parseInt(st.nextToken());
			y2=Integer.parseInt(st.nextToken());
			
			sb.append(accumulate[x2][y2]-accumulate[x2][y1-1]-accumulate[x1-1][y2]+accumulate[x1-1][y1-1]+"\n");
		}

		System.out.println(sb.toString());
	}
}

728x90

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

<백준 알고리즘> 18111번: 마인크래프트 (1)	2023.01.22
<백준 알고리즘> 15829번: Hashing (0)	2023.01.22
<백준 알고리즘> 11659번: 구간 합 구하기 4 (0)	2023.01.21
<백준 알고리즘> 4949번: 균형잡힌 세상 (0)	2023.01.21
<백준 알고리즘> 2805번: 나무 자르기 (0)	2023.01.21

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
1 ≤ i ≤ j ≤ N

예제 입력 1

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

예제 출력 1

12
9
1

Solution

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

int main(void)
{
	int N, M, i, j, *arr=NULL, *accumulate=NULL;

	scanf("%d%d", &N, &M);
	arr=(int *)malloc(N*sizeof(int));
	accumulate=(int *)calloc(N,sizeof(int));

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

	for(int m=0;m<M;m++)
	{
		scanf("%d%d", &i, &j);
		printf("%d\n", accumulate[j-1]-accumulate[i-1]+arr[i-1]);
	}

	free(arr);
	free(accumulate);
	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 IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		int[] arr=new int[N];
		int[] accumulate=new int[N];
		int i, j;
		
		st=new StringTokenizer(br.readLine());
		accumulate[0]=arr[0]=Integer.parseInt(st.nextToken());
		for(int n=1;n<N;n++) {
			arr[n]=Integer.parseInt(st.nextToken());
			accumulate[n]=accumulate[n-1]+arr[n];
		}

		for(int m=0;m<M;m++) {
			st=new StringTokenizer(br.readLine());
			i=Integer.parseInt(st.nextToken());
			j=Integer.parseInt(st.nextToken());
			sb.append(accumulate[j-1]-accumulate[i-1]+arr[i-1]+"\n");
		}

		System.out.println(sb.toString());
	}
}

728x90

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

<백준 알고리즘> 15829번: Hashing (0)	2023.01.22
<백준 알고리즘> 11660번: 구간 합 구하기 5 (0)	2023.01.22
<백준 알고리즘> 4949번: 균형잡힌 세상 (0)	2023.01.21
<백준 알고리즘> 2805번: 나무 자르기 (0)	2023.01.21
<백준 알고리즘> 10158번: 개미 (0)	2023.01.18

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다.

입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

예제 입력 1

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
.
.

예제 출력 1

yes
yes
no
no
no
yes
yes

힌트

7번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.

Solution

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

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

	gets(str);
	while(strcmp(str,".")!=0)
	{
		int check[101]={0, }, current=0;
		bool able=true;

		for(int i=0;str[i]!='.';i++)
		{
			switch(str[i])
			{
				case '(':
					check[current++]=1;
					break;
				case '[':
					check[current++]=2;
					break;
				case ')':
					if(current==0)
						able=false;
					else if(check[--current]!=1)
						able=false;
					break;
				case ']':
					if(current==0)
						able=false;
					else if(check[--current]!=2)
						able=false;
					break;
			}
			if(!able)
				break;
		}

		printf("%s\n", able&&current==0?"yes":"no");

		for(int i=0;i<101;i++)
			str[i]='\0';
		gets(str);
	}

	return 0;
}

728x90

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

<백준 알고리즘> 11660번: 구간 합 구하기 5 (0)	2023.01.22
<백준 알고리즘> 11659번: 구간 합 구하기 4 (0)	2023.01.21
<백준 알고리즘> 2805번: 나무 자르기 (0)	2023.01.21
<백준 알고리즘> 10158번: 개미 (0)	2023.01.18
<백준 알고리즘> 2567번: 색종이 - 2 (0)	2023.01.18

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

예제 입력 1

4 7
20 15 10 17

예제 출력 1

15

예제 입력 2

5 20
4 42 40 26 46

예제 출력 2

36

Solution

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

bool able(long long *tree,long long N,long long M,long long mid)
{
	long long sum=0;

	for(long long n=0;n<N;n++)
		sum+=tree[n]-mid>0?tree[n]-mid:0;

	return sum>=M;
}

int main(void)
{
	long long N, M, *tree=NULL, low=0, high=1000000000;

	scanf("%lld%lld", &N, &M);
	tree=(long long *)malloc(N*sizeof(long long));

	for(long long n=0;n<N;n++)
		scanf("%lld", &tree[n]);

	while(low<=high)
	{
		long long mid=(low+high)/2;

		if(able(tree,N,M,mid))
			low=mid+1;
		else
			high=mid-1;
	}

	printf("%lld\n", high);
	free(tree);
	return 0;
}

728x90

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

<백준 알고리즘> 11659번: 구간 합 구하기 4 (0)	2023.01.21
<백준 알고리즘> 4949번: 균형잡힌 세상 (0)	2023.01.21
<백준 알고리즘> 10158번: 개미 (0)	2023.01.18
<백준 알고리즘> 2567번: 색종이 - 2 (0)	2023.01.18
<백준 알고리즘> 2527번: 직사각형 (0)	2023.01.18