서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

입력

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

출력

첫째 줄에 자연수 N의 최댓값을 출력한다.

예제 입력 1

200

예제 출력 1

19
더보기

Solution

#include<stdio.h>

int main(void)
{
	long long S, N=1;

	scanf("%lld", &S);

	while(N++)
		if(N*(N+1)/2>S)
			break;

	printf("%lld\n", N-1);
	return 0;
}
728x90

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

<백준 알고리즘> 16926번: 배열 돌리기 1  (0) 2023.02.14
<백준 알고리즘> 11025번: 요세푸스 문제 3  (0) 2023.02.13
<백준 알고리즘> 17406번: 배열 돌리기 4  (0) 2023.02.13
<백준 알고리즘> 1991번: 트리 순회  (0) 2023.02.12
<백준 알고리즘> 2304번: 창고 다각형  (0) 2023.02.12

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.

1 2 3
2 1 1
4 5 6

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

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

A[6][1]   A[6][2]   A[6][3]   A[6][4]   A[6][5]   A[6][6]

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3		 1 8 2 3 2 5
3 2 3 7 2 6
8 4 5 1 1 3
3 3 1 1 4 5
9 2 1 4 3 1		 1 8 2 3 2 5
3 2 3 7 2 6
3 8 4 1 1 3
9 3 5 1 4 5
2 1 1 4 3 1
배열 A (3, 4, 2) 연산 수행 후 (4, 2, 1) 연산 수행 후
1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3		 1 2 3 2 5 6
3 8 7 2 1 3
3 8 2 1 4 5
9 4 3 1 1 1
3 2 5 1 4 3		 1 8 2 3 2 5
3 8 2 7 2 6
3 4 3 1 1 3
9 2 1 1 4 5
3 5 1 4 3 1
배열 A (4, 2, 1) 연산 수행 후 (3, 4, 2) 연산 수행 후

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

입력

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

출력

배열 A의 값의 최솟값을 출력한다.

제한

  • 3 ≤ N, M ≤ 50
  • 1 ≤ K ≤ 6
  • 1 ≤ A[i][j] ≤ 100
  • 1 ≤ s
  • 1 ≤ r-s < r < r+s ≤ N
  • 1 ≤ c-s < c < c+s ≤ M

예제 입력 1

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

예제 출력 1

12
더보기

Solution

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

int N, M, K, *r=NULL, *c=NULL, *s=NULL;

int rotate(int **A,int bit)
{
	int min[65], count=0, min_value=10000, original_min=10000;

	if(bit==(1<<K)-1)
	{
		for(int n=0;n<N;n++)
		{
			int sum=0;

			for(int m=0;m<M;m++)
				sum+=A[n][m];

			if(sum<original_min)
				original_min=sum;
		}
		return original_min;
	}

	for(int k=0;k<K;k++)
		if(!(bit&1<<k))
		{
			int **B=(int **)malloc(N*sizeof(int *));
			for(int n=0;n<N;n++)
			{
				B[n]=(int *)malloc(M*sizeof(int));
				for(int m=0;m<M;m++)
					B[n][m]=A[n][m];
			}

			for(int i=1;i<=s[k];i++)
			{
				int temp=B[r[k]-i][c[k]+i];

				for(int j=0;j<2*i;j++)
					B[r[k]-i][c[k]+i-j]=B[r[k]-i][c[k]+i-j-1];
				for(int j=0;j<2*i;j++)
					B[r[k]-i+j][c[k]-i]=B[r[k]-i+j+1][c[k]-i];
				for(int j=0;j<2*i;j++)
					B[r[k]+i][c[k]-i+j]=B[r[k]+i][c[k]-i+j+1];
				for(int j=0;j<2*i;j++)
					B[r[k]+i-j][c[k]+i]=B[r[k]+i-j-1][c[k]+i];
				B[r[k]-i+1][c[k]+i]=temp;
			}

			min[count++]=rotate(B,bit|1<<k);

			for(int n=0;n<N;n++)
				free(B[n]);
			free(B);
		}

	for(int i=0;i<count;i++)
		if(min[i]<min_value)
			min_value=min[i];

	return min_value;
}

int main(void)
{
	int **A=NULL;

	scanf("%d%d%d", &N, &M, &K);
	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]);
	}
	r=(int *)malloc(K*sizeof(int));
	c=(int *)malloc(K*sizeof(int));
	s=(int *)malloc(K*sizeof(int));

	for(int k=0;k<K;k++)
	{
		scanf("%d%d%d", &r[k], &c[k], &s[k]);
		r[k]--;
		c[k]--;
	}
	printf("%d\n", rotate(A,0));

	free(s);
	free(c);
	free(r);
	for(int n=0;n<N;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 {
	static int N, M, K;
	static int[] r, c, s;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		K=Integer.parseInt(st.nextToken());
		int[][] A=new int[N][M];
		r=new int[K];
		c=new int[K];
		s=new int[K];
		
		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 k=0;k<K;k++) {
			st=new StringTokenizer(br.readLine());
			r[k]=Integer.parseInt(st.nextToken())-1;
			c[k]=Integer.parseInt(st.nextToken())-1;
			s[k]=Integer.parseInt(st.nextToken());
		}

		System.out.println(rotate(A,0));
	}
	
	static int rotate(int[][] A,int bit) {
		int count=0, minValue=10000, originalMin=10000;
		int[] min=new int[64];
		
		if(bit==(1<<K)-1) {
			for(int n=0;n<N;n++) {
				int sum=0;
				
				for(int m=0;m<M;m++)
					sum+=A[n][m];
				
				if(sum<originalMin)
					originalMin=sum;
			}
			return originalMin;
		}
		
		for(int k=0;k<K;k++)
			if((bit&(1<<k))==0) {
				int[][] B=new int[N][M];
				for(int n=0;n<N;n++)
					for(int m=0;m<M;m++)
						B[n][m]=A[n][m];
				
				for(int i=1;i<=s[k];i++) {
					int temp=B[r[k]-i][c[k]+i];

					for(int j=0;j<2*i;j++)
						B[r[k]-i][c[k]+i-j]=B[r[k]-i][c[k]+i-j-1];
					for(int j=0;j<2*i;j++)
						B[r[k]-i+j][c[k]-i]=B[r[k]-i+j+1][c[k]-i];
					for(int j=0;j<2*i;j++)
						B[r[k]+i][c[k]-i+j]=B[r[k]+i][c[k]-i+j+1];
					for(int j=0;j<2*i;j++)
						B[r[k]+i-j][c[k]+i]=B[r[k]+i-j-1][c[k]+i];
					B[r[k]-i+1][c[k]+i]=temp;
				}
				
				min[count++]=rotate(B,bit|(1<<k));
			}
		
		for(int i=0;i<count;i++)
			if(min[i]<minValue)
				minValue=min[i];
		
		return minValue;
	}
}

 

728x90

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

<백준 알고리즘> 11025번: 요세푸스 문제 3  (0) 2023.02.13
<백준 알고리즘> 1789번: 수들의 합  (0) 2023.02.13
<백준 알고리즘> 1991번: 트리 순회  (0) 2023.02.12
<백준 알고리즘> 2304번: 창고 다각형  (0) 2023.02.12
<백준 알고리즘> 1931번: 회의실 배정  (0) 2023.02.12

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

  • 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
  • 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
  • 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

예제 입력 1

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

예제 출력 1

ABDCEFG
DBAECFG
DBEGFCA
더보기

Solution

#include<stdio.h>

char tree_info[26][3]={'\0', };

void preorder(int current)
{
	printf("%c", current+'A');

	if(tree_info[current][1]!='\0')
		preorder(tree_info[current][1]-'A');
	if(tree_info[current][2]!='\0')
		preorder(tree_info[current][2]-'A');
}

void inorder(int current)
{
	if(tree_info[current][1]!='\0')
		inorder(tree_info[current][1]-'A');
	printf("%c", current+'A');
	if(tree_info[current][2]!='\0')
		inorder(tree_info[current][2]-'A');
}

void postorder(int current)
{
	if(tree_info[current][1]!='\0')
		postorder(tree_info[current][1]-'A');
	if(tree_info[current][2]!='\0')
		postorder(tree_info[current][2]-'A');
	printf("%c", current+'A');
}

int main(void)
{
	int N;
	char parent, child[2];

	scanf("%d", &N);

	getchar();
	for(int n=0;n<N;n++)
	{
		scanf("%c", &parent);
		getchar();
		for(int i=0;i<2;i++)
		{
			scanf("%c", &child[i]);
			getchar();

			if(child[i]!='.')
			{
				tree_info[parent-'A'][i+1]=child[i];
				tree_info[child[i]-'A'][0]=parent;
			}
		}
	}

	for(int i=0;i<N;i++)
		if(tree_info[i][0]=='\0')
		{
			preorder(i);
			printf("\n");
			inorder(i);
			printf("\n");
			postorder(i);
			printf("\n");
		}

	return 0;
}
더보기

Solution

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

public class Main {
	static char[][] treeInfo=new char[26][3];
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String str;
		
		int N=Integer.parseInt(br.readLine());
		char parent;
		char[] child=new char[2];
		
		for(int n=0;n<N;n++) {
			str=br.readLine();
			parent=str.charAt(0);
			for(int i=0;i<2;i++) {
				child[i]=str.charAt(i*2+2);
				
				if(child[i]!='.') {
					treeInfo[(int)(parent-'A')][i+1]=child[i];
					treeInfo[(int)(child[i]-'A')][0]=parent;
				}
			}
		}
		
		for(int n=0;n<N;n++)
			if(treeInfo[n][0]==0) {
				preorder(n);
				sb.append("\n");
				inorder(n);
				sb.append("\n");
				postorder(n);
				sb.append("\n");
			}

		System.out.println(sb.toString());
	}
	
	static void preorder(int current)
	{
		sb.append((char)(current+'A'));

		if(treeInfo[current][1]!=0)
			preorder(treeInfo[current][1]-'A');
		if(treeInfo[current][2]!='\0')
			preorder(treeInfo[current][2]-'A');
	}

	static void inorder(int current)
	{
		if(treeInfo[current][1]!=0)
			inorder(treeInfo[current][1]-'A');
		sb.append((char)(current+'A'));
		if(treeInfo[current][2]!='\0')
			inorder(treeInfo[current][2]-'A');
	}

	static void postorder(int current)
	{
		if(treeInfo[current][1]!='\0')
			postorder(treeInfo[current][1]-'A');
		if(treeInfo[current][2]!='\0')
			postorder(treeInfo[current][2]-'A');
		sb.append((char)(current+'A'));
	}
}

 

728x90

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

<백준 알고리즘> 1789번: 수들의 합  (0) 2023.02.13
<백준 알고리즘> 17406번: 배열 돌리기 4  (0) 2023.02.13
<백준 알고리즘> 2304번: 창고 다각형  (0) 2023.02.12
<백준 알고리즘> 1931번: 회의실 배정  (0) 2023.02.12
<백준 알고리즘> 2023번: 신기한 소수  (0) 2023.02.10

N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.

  1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
  2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
  3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
  4. 지붕의 가장자리는 땅에 닿아야 한다.
  5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

그림1 . 기둥과 지붕(굵은 선)의 예

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.

출력

첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.

예제 입력 1

7
2 4
11 4
15 8
4 6
5 3
8 10
13 6

예제 출력 1

98
더보기

Solution

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

int main(void)
{
	int N, pillar[1001]={0, }, *left=NULL, *right=NULL, L, H, left_current=1, right_current=1, area=0;

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

	for(int n=0;n<N;n++)
	{
		scanf("%d%d", &L, &H);
		pillar[L]=H;
	}

	left[0]=0;
	for(int n=0;n<1001;n++)
		if(pillar[n]>pillar[left[left_current-1]])
			left[left_current++]=n;

	right[0]=1000;
	for(int n=1000;n>=0;n--)
		if(pillar[n]>pillar[right[right_current-1]])
			right[right_current++]=n;

	for(int i=1;i<left_current;i++)
		area+=(left[i]-left[i-1])*pillar[left[i-1]];
	for(int i=1;i<right_current;i++)
		area+=(right[i-1]-right[i])*pillar[right[i-1]];
	area+=(right[right_current-1]-left[left_current-1]+1)*pillar[left[left_current-1]];

	printf("%d\n", area);
	free(right);
	free(left);
	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));
		StringTokenizer st;

		int N=Integer.parseInt(br.readLine()), L, H, left_current=1, right_current=1, area=0;
		int[] left=new int[N+1], right=new int[N+1], pillar=new int[1001];
		
		for(int n=0;n<N;n++) {
			st=new StringTokenizer(br.readLine());
			L=Integer.parseInt(st.nextToken());
			H=Integer.parseInt(st.nextToken());
			pillar[L]=H;
		}
		
		for(int n=0;n<1001;n++)
			if(pillar[n]>pillar[left[left_current-1]])
				left[left_current++]=n;
		
		right[0]=1000;
		for(int n=1000;n>=0;n--)
			if(pillar[n]>pillar[right[right_current-1]])
				right[right_current++]=n;

		for(int i=1;i<left_current;i++)
			area+=(left[i]-left[i-1])*pillar[left[i-1]];
		for(int i=1;i<right_current;i++)
			area+=(right[i-1]-right[i])*pillar[right[i-1]];
		area+=(right[right_current-1]-left[left_current-1]+1)*pillar[left[left_current-1]];
		
		System.out.println(area);
	}
}

 

728x90

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

<백준 알고리즘> 17406번: 배열 돌리기 4  (0) 2023.02.13
<백준 알고리즘> 1991번: 트리 순회  (0) 2023.02.12
<백준 알고리즘> 1931번: 회의실 배정  (0) 2023.02.12
<백준 알고리즘> 2023번: 신기한 소수  (0) 2023.02.10
<백준 알고리즘> 2961번: 도영이가 만든 맛있는 음식  (0) 2023.02.09

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1

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

예제 출력 1

4

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

더보기

Solution

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

int stemp[100000], etemp[100000];

void merge(int *start,int *end,int left,int right,int mid)
{
	int i=left, j=mid+1;

	for(int k=left;k<=right;k++)
		if(j>right)
		{
			stemp[k]=start[i];
			etemp[k]=end[i];
			i++;
		}
		else if(i>mid)
		{
			stemp[k]=start[j];
			etemp[k]=end[j];
			j++;
		}
		else if(end[i]<end[j] || end[i]==end[j] && start[i]<start[j])
		{
			stemp[k]=start[i];
			etemp[k]=end[i];
			i++;
		}
		else
		{
			stemp[k]=start[j];
			etemp[k]=end[j];
			j++;
		}

	for(int k=left;k<=right;k++)
	{
		start[k]=stemp[k];
		end[k]=etemp[k];
	}
}

void mergesort(int *start,int *end,int left,int right)
{
	if(left<right)
	{
		int mid=(left+right)/2;
		mergesort(start,end,left,mid);
		mergesort(start,end,mid+1,right);
		merge(start,end,left,right,mid);
	}
}

int main(void)
{
	int N, *start=NULL, *end=NULL, count=0, last=-1;

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

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

	mergesort(start,end,0,N-1);

	for(int n=0;n<N;n++)
		if(start[n]>=last)
		{
			count++;
			last=end[n];
		}

	printf("%d\n", count);
	free(start);
	free(end);
	return 0;
}
더보기

Solution

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

public class Main {
	static int[] start, end, stemp, etemp;
	
	static void merge(int left,int right) {
		int i=left, mid=(left+right)/2, j=mid+1;
		
		for(int k=left;k<=right;k++)
			if(j>right) {
				stemp[k]=start[i];
				etemp[k]=end[i++];
			}
			else if(i>mid || end[i]>end[j] || end[i]==end[j] && start[i]>start[j]) {
				stemp[k]=start[j];
				etemp[k]=end[j++];
			}
			else {
				stemp[k]=start[i];
				etemp[k]=end[i++];
			}
		
		for(int k=left;k<=right;k++) {
			start[k]=stemp[k];
			end[k]=etemp[k];
		}
	}
	
	static void mergeSort(int left,int right) {
		if(left<right) {
			int mid=(left+right)/2;
			mergeSort(left,mid);
			mergeSort(mid+1,right);
			merge(left,right);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N=Integer.parseInt(br.readLine()), count=0, last=-1;
		start=new int[N];
		end=new int[N];
		stemp=new int[N];
		etemp=new int[N];
		
		for(int n=0;n<N;n++) {
			st=new StringTokenizer(br.readLine());
			start[n]=Integer.parseInt(st.nextToken());
			end[n]=Integer.parseInt(st.nextToken());
		}
		
		mergeSort(0,N-1);
		
		for(int n=0;n<N;n++)
			if(start[n]>=last) {
				count++;
				last=end[n];
			}

		System.out.println(count);
	}
}

 

728x90

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

<백준 알고리즘> 1991번: 트리 순회  (0) 2023.02.12
<백준 알고리즘> 2304번: 창고 다각형  (0) 2023.02.12
<백준 알고리즘> 2023번: 신기한 소수  (0) 2023.02.10
<백준 알고리즘> 2961번: 도영이가 만든 맛있는 음식  (0) 2023.02.09
<백준 알고리즘> 11725번: 트리의 부모 찾기  (0) 2023.02.09

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

예제 입력 1

4

예제 출력 1

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
더보기

Solution

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

int min=1;
bool prime[8]={false,false,true,true,false,true,false,true};

bool is_prime(int n)
{
	if(n<2)
		return false;
	else if(n==2)
		return true;
	else if(n%2==0)
		return false;
	else
		for(int i=3;i*i<=n;i+=2)
			if(n%i==0)
				return false;
	return true;
}

void amazing_prime(int num)
{
	if(num>min)
	{
		printf("%d\n", num);
		return;
	}

	if(num==0)
	{
		for(int i=2;i<8;i++)
			if(prime[i])
				amazing_prime(i);
		return;
	}

	for(int i=1;i<10;i+=2)
		if(is_prime(10*num+i))
			amazing_prime(10*num+i);
}

int main(void)
{
	int N;

	scanf("%d", &N);
	for(int n=1;n<N;n++)
		min*=10;

	amazing_prime(0);

	return 0;
}
728x90

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

<백준 알고리즘> 2304번: 창고 다각형  (0) 2023.02.12
<백준 알고리즘> 1931번: 회의실 배정  (0) 2023.02.12
<백준 알고리즘> 2961번: 도영이가 만든 맛있는 음식  (0) 2023.02.09
<백준 알고리즘> 11725번: 트리의 부모 찾기  (0) 2023.02.09
<백준 알고리즘> 12865번: 평범한 배낭  (0) 2023.02.09

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

입력

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다. 

예제 입력 1

1
3 10

예제 출력 1

7

예제 입력 2

2
3 8
5 8

예제 출력 2

1

예제 입력 3

4
1 7
2 6
3 8
4 9

예제 출력 3

1

2, 3, 4번 재료를 사용한다면, 요리의 신맛은 2×3×4=24, 쓴맛은 6+8+9=23이 된다. 차이는 1이다.

더보기

Solution

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

int N, S[10], B[10];

int food(int current,int set)
{
	if(current==N)
	{
		if(set>0)
		{
			int s=1, b=0;

			for(int n=0;n<N;n++)
				if(set & 1<<n)
				{
					s*=S[n];
					b+=B[n];
				}

			return s-b>=0?s-b:b-s;
		}
		return 1000000000;
	}

	int used=food(current+1,set|1<<current);
	int unused=food(current+1,set);

	return used<unused?used:unused;
}

int main(void)
{
	scanf("%d", &N);

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

	printf("%d\n", food(0,0));
	return 0;
}
728x90

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

<백준 알고리즘> 1931번: 회의실 배정  (0) 2023.02.12
<백준 알고리즘> 2023번: 신기한 소수  (0) 2023.02.10
<백준 알고리즘> 11725번: 트리의 부모 찾기  (0) 2023.02.09
<백준 알고리즘> 12865번: 평범한 배낭  (0) 2023.02.09
<백준 알고리즘> 16953번: A → B  (0) 2023.02.08

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1

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

예제 출력 1

4
6
1
3
1
4

예제 입력 2

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

예제 출력 2

1
1
2
3
3
4
4
5
5
6
6
더보기

Solution

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

int main(void)
{
	int N, **connected=NULL, *connected_count=NULL, **tree=NULL, *queue=NULL, *parent=NULL, front=0, rear=0;

	scanf("%d", &N);
	connected=(int **)malloc((N-1)*sizeof(int *));
	for(int n=0;n<N-1;n++)
		connected[n]=(int *)malloc(2*sizeof(int));
	connected_count=(int *)calloc(N+1,sizeof(int));
	parent=(int *)calloc(N+1,sizeof(int));
	tree=(int **)malloc((N+1)*sizeof(int *));
	queue=(int *)malloc(N*sizeof(int));
	for(int i=0;i<N-1;i++)
	{
		scanf("%d%d", &connected[i][0], &connected[i][1]);
		if(connected[i][0]==1)
		{
			parent[connected[i][1]]=1;
			queue[rear++]=connected[i][1];
		}
		else if(connected[i][1]==1)
		{
			parent[connected[i][0]]=1;
			queue[rear++]=connected[i][0];
		}
		else
		{
			connected_count[connected[i][0]]++;
			connected_count[connected[i][1]]++;
		}
	}

	for(int i=1;i<=N;i++)
		tree[i]=(int *)calloc(connected_count[i],sizeof(int));

	for(int i=0;i<=N;i++)
		connected_count[i]=0;

	for(int i=0;i<N-1;i++)
	{
		if(connected[i][0]!=1 && connected[i][1]!=1)
		{
			tree[connected[i][0]][connected_count[connected[i][0]]++]=connected[i][1];
			tree[connected[i][1]][connected_count[connected[i][1]]++]=connected[i][0];
		}
	}

	while(front<rear)
	{
		for(int i=0;i<connected_count[queue[front]];i++)
			if(parent[tree[queue[front]][i]]==0)
			{
				parent[tree[queue[front]][i]]=queue[front];
				queue[rear++]=tree[queue[front]][i];
			}
		front++;
	}

	for(int i=2;i<=N;i++)
		printf("%d\n", parent[i]);
	for(int i=1;i<=N;i++)
		free(tree[i]);
	free(tree);
	free(queue);
	free(parent);
	free(connected_count);
	for(int n=0;n<N-1;n++)
		free(connected[n]);
	free(connected);
	return 0;
}
728x90

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

<백준 알고리즘> 2023번: 신기한 소수  (0) 2023.02.10
<백준 알고리즘> 2961번: 도영이가 만든 맛있는 음식  (0) 2023.02.09
<백준 알고리즘> 12865번: 평범한 배낭  (0) 2023.02.09
<백준 알고리즘> 16953번: A → B  (0) 2023.02.08
<백준 알고리즘> 17298번: 오큰수  (0) 2023.02.08

+ Recent posts

티스토리툴바