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

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 N Combination K를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)

출력

N Combination K를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

5 2

예제 출력 1

10

Solution

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

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

	scanf("%d %d", &N, &K);
	C=(int **)malloc((N+1)*sizeof(int *));
	K=K*2>=N?N-K:K;
	for(int c=0;c<=N;c++)
		C[c]=(int *)calloc(K+1,sizeof(int));

	C[0][0]=1;
	for(int i=1;i<=N;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=K;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%10007;
	}

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

728x90

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

<백준 알고리즘> 2193번: 이친수 (0)	2021.02.13
<백준 알고리즘> 1747번: 소수&팰린드롬 (0)	2021.02.09
<백준 알고리즘> 2579번: 계단 오르기 (0)	2021.02.08
<백준 알고리즘> 2947번: 나무 조각 (0)	2021.02.05
<백준 알고리즘> 1568번: 새 (0)	2021.02.05

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력 1

6
10
20
15
25
10
20

예제 출력 1

75

Solution

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

int max(int x,int y)
{
	return x>y?x:y;
}

int main(void)
{
	int *stairs=NULL, num, **score=NULL;

	scanf("%d", &num);
	stairs=(int *)calloc(num+1,sizeof(int));
	score=(int **)malloc((num+1)*sizeof(int *));
	for(int i=0;i<=num;i++)
		score[i]=(int *)calloc(2,sizeof(int));

	for(int i=1;i<=num;i++)
		scanf("%d", &stairs[i]);

	score[1][0]=stairs[1];
	for(int i=2;i<=num;i++)
	{
		score[i][0]=stairs[i]+max(score[i-2][0],score[i-2][1]);
		score[i][1]=stairs[i]+score[i-1][0];
	}

	printf("%d\n", max(score[num][0],score[num][1]));
	for(int i=0;i<=num;i++)
		free(score[i]);
	free(score);
	free(stairs);
	return 0;
}

728x90

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

<백준 알고리즘> 1747번: 소수&팰린드롬 (0)	2021.02.09
<백준 알고리즘> 11051번: 이항 계수 2 (0)	2021.02.08
<백준 알고리즘> 2947번: 나무 조각 (0)	2021.02.05
<백준 알고리즘> 1568번: 새 (0)	2021.02.05
<백준 알고리즘> 9375번: 패션왕 신해빈 (0)	2021.02.05

문제

동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 쓰여 있다.

동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다.

첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 1 단계로 다시 간다.

처음 조각의 순서가 주어졌을 때, 위치를 바꿀 때 마다 조각의 순서를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 조각에 쓰여 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다.

출력

두 조각의 순서가 바뀔때 마다 조각의 순서를 출력한다.

예제 입력 1

2 1 5 3 4

예제 출력 1

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

Solution

#include<stdio.h>

#define swap(x,y,temp) {temp=x;x=y;y=temp;}

int main(void)
{
	int tree[5], temp;

	for(int i=0;i<5;i++)
		scanf("%d", &tree[i]);

	while(tree[0]!=1 || tree[1]!=2 || tree[2]!=3 || tree[3]!=4 || tree[4]!=5)
	{
		if(tree[0]>tree[1])
		{
			swap(tree[0],tree[1],temp);

			for(int i=0;i<5;i++)
				printf("%d ", tree[i]);
            printf("\n");
        }
        if(tree[1]>tree[2])
        {
			swap(tree[1],tree[2],temp);

            for(int i=0;i<5;i++)
                printf("%d ", tree[i]);
            printf("\n");
        }
        if(tree[2]>tree[3])
        {
			swap(tree[2],tree[3],temp);

            for(int i=0;i<5;i++)
                printf("%d ", tree[i]);
            printf("\n");
        }
        if(tree[3]>tree[4])
        {
			swap(tree[3],tree[4],temp);

            for(int i=0;i<5;i++)
                printf("%d ", tree[i]);
            printf("\n");
        }
    }

    return 0;
}

728x90

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

<백준 알고리즘> 11051번: 이항 계수 2 (0)	2021.02.08
<백준 알고리즘> 2579번: 계단 오르기 (0)	2021.02.08
<백준 알고리즘> 1568번: 새 (0)	2021.02.05
<백준 알고리즘> 9375번: 패션왕 신해빈 (0)	2021.02.05
<백준 알고리즘> 2738번: 행렬 덧셈 (0)	2021.02.05

문제

N마리의 새가 나무에 앉아있고, 자연수를 배우기 원한다. 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 어떤 숫자 K를 노래할 때, K마리의 새가 나무에서 하늘을 향해 날아간다. 만약, 현재 나무에 앉아있는 새의 수가 지금 불러야 하는 수 보다 작을 때는, 1부터 게임을 다시 시작한다.

나무에 앉아 있는 새의 수 N이 주어질 때, 하나의 수를 노래하는데 1초가 걸린다고 하면, 모든 새가 날아가기까지 총 몇 초가 걸리는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 새의 수 N이 주어진다. 이 값은 10^9보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 1

14

예제 출력 1

8

Solution

#include<stdio.h>

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

	scanf("%d", &N);

	while(N>0)
	{
		K=N>K?K+1:1;
		N-=K;
		count++;
	}

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

728x90

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

<백준 알고리즘> 2579번: 계단 오르기 (0)	2021.02.08
<백준 알고리즘> 2947번: 나무 조각 (0)	2021.02.05
<백준 알고리즘> 9375번: 패션왕 신해빈 (0)	2021.02.05
<백준 알고리즘> 2738번: 행렬 덧셈 (0)	2021.02.05
<백준 알고리즘> 5576번: 콘테스트 (0)	2021.02.04

문제

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

출력

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

예제 입력 1

2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

예제 출력 1

5
3

힌트

첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다.

Solution

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

int main(void)
{
	int t;

	scanf("%d", &t);

	for(int test_case=0;test_case<t;test_case++)
	{
		char **cloth=NULL, temp[21]={'\0', };
		int n, *num=NULL;
		long long int mul=1;

		scanf("%d", &n);
		num=(int *)calloc(n,sizeof(int));
		cloth=(char **)malloc(n*sizeof(char *));
		for(int i=0;i<n;i++)
		{
			bool same=false;

			cloth[i]=(char *)calloc(21,sizeof(char));
			scanf("%s %s", temp, cloth[i]);

			for(int j=0;j<i;j++)
				if(strcmp(cloth[i],cloth[j])==0)
				{
					same=true;
					num[j]++;
					break;
				}
			if(!same)
				num[i]++;
		}

		for(int i=0;i<n;i++)
			mul*=(num[i]+1);

		printf("%lld\n", mul-1);
		for(int i=0;i<n;i++)
			free(cloth[i]);
		free(cloth);
		free(num);
	}

	return 0;
}

728x90

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

<백준 알고리즘> 2947번: 나무 조각 (0)	2021.02.05
<백준 알고리즘> 1568번: 새 (0)	2021.02.05
<백준 알고리즘> 2738번: 행렬 덧셈 (0)	2021.02.05
<백준 알고리즘> 5576번: 콘테스트 (0)	2021.02.04
<백준 알고리즘> 13300번: 방 배정 (0)	2021.02.04

문제

N*M크기의 두 행렬 A와 B가 주어졌을 때, 두 행렬을 더하는 프로그램을 작성하시오.

입력

첫째 줄에 행렬의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 차례대로 주어진다. 이어서 N개의 줄에 행렬 B의 원소 M개가 차례대로 주어진다. N과 M은 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다.

출력

첫째 줄부터 N개의 줄에 행렬 A와 B를 더한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다.

예제 입력 1

3 3
1 1 1
2 2 2
0 1 0
3 3 3
4 4 4
5 5 100

예제 출력 1

4 4 4
6 6 6
5 6 100

Solution

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

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

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

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

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

728x90

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

<백준 알고리즘> 1568번: 새 (0)	2021.02.05
<백준 알고리즘> 9375번: 패션왕 신해빈 (0)	2021.02.05
<백준 알고리즘> 5576번: 콘테스트 (0)	2021.02.04
<백준 알고리즘> 13300번: 방 배정 (0)	2021.02.04
<백준 알고리즘> 2846번: 오르막길 (0)	2021.02.04

문제

최근 온라인에서의 프로그래밍 콘테스트가 열렸다. W 대학과 K 대학의 컴퓨터 클럽은 이전부터 라이벌 관계에있어,이 콘테스트를 이용하여 양자의 우열을 정하자라는 것이되었다.

이번이 두 대학에서 모두 10 명씩이 콘테스트에 참여했다. 긴 논의 끝에 참가한 10 명 중 득점이 높은 사람에서 3 명의 점수를 합산하여 대학의 득점으로하기로 했다.

W 대학 및 K 대학 참가자의 점수 데이터가 주어진다. 이때, 각각의 대학의 점수를 계산하는 프로그램을 작성하라.

입력

입력은 20 행으로 구성된다. 1 번째 줄부터 10 번째 줄에는 W 대학의 각 참가자의 점수를 나타내는 정수가 11 번째 줄부터 20 번째 줄에는 K 대학의 각 참가자의 점수를 나타내는 정수가 적혀있다. 이 정수는 모두 0 이상 100 이하이다.

출력

W 대학 점수와 K 대학의 점수를 순서대로 공백으로 구분하여 출력하라.

예제 입력 1

23
23
20
15
15
14
13
9
7
6
25
19
17
17
16
13
12
11
9
5

예제 출력 1

66 61

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 W[10], K[10];

	for(int w=0;w<10;w++)
		scanf("%d", &W[w]);
	for(int k=0;k<10;k++)
		scanf("%d", &K[k]);

	qsort((void *)W,(size_t)10,sizeof(int),compare);
	qsort((void *)K,(size_t)10,sizeof(int),compare);

	printf("%d %d\n", W[7]+W[8]+W[9], K[7]+K[8]+K[9]);
	return 0;
}

728x90

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

<백준 알고리즘> 9375번: 패션왕 신해빈 (0)	2021.02.05
<백준 알고리즘> 2738번: 행렬 덧셈 (0)	2021.02.05
<백준 알고리즘> 13300번: 방 배정 (0)	2021.02.04
<백준 알고리즘> 2846번: 오르막길 (0)	2021.02.04
<백준 알고리즘> 5598번: 카이사르 암호 (0)	2021.02.04

문제

정보 초등학교에서는 단체로 2박 3일 수학여행을 가기로 했다. 여러 학년이 같은 장소로 수학여행을 가려고 하는데 1학년부터 6학년까지 학생들이 묵을 방을 배정해야 한다. 남학생은 남학생끼리, 여학생은 여학생끼리 방을 배정해야 한다. 또한 한 방에는 같은 학년의 학생들을 배정해야 한다. 물론 한 방에 한 명만 배정하는 것도 가능하다.

한 방에 배정할 수 있는 최대 인원 수 K가 주어졌을 때, 조건에 맞게 모든 학생을 배정하기 위해 필요한 방의 최소 개수를 구하는 프로그램을 작성하시오.

예를 들어, 수학여행을 가는 학생이 다음과 같고 K = 2일 때 12개의 방이 필요하다. 왜냐하면 3학년 남학생을 배정하기 위해 방 두 개가 필요하고 4학년 여학생에는 방을 배정하지 않아도 되기 때문이다.

학년	여학생	남학생
1학년	영희	동호, 동진
2학년	혜진, 상희	경수
3학년	경희	동수, 상철, 칠복
4학년		달호
5학년	정숙	호동, 건우
6학년	수지	동건

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수학여행에 참가하는 학생 수를 나타내는 정수 N(1 ≤ N ≤ 1,000)과 한 방에 배정할 수 있는 최대 인원 수 K(1 < K ≤ 1,000)가 공백으로 분리되어 주어진다. 다음 N 개의 각 줄에는 학생의 성별 S와 학년 Y(1 ≤ Y ≤ 6)가 공백으로 분리되어 주어진다. 성별 S는 0, 1중 하나로서 여학생인 경우에 0, 남학생인 경우에 1로 나타낸다.

출력

표준 출력으로 학생들을 모두 배정하기 위해 필요한 최소한의 방의 수를 출력한다.

예제 입력 1

16 2
1 1
0 1
1 1
0 2
1 2
0 2
0 3
1 3
1 4
1 3
1 3
0 6
1 5
0 5
1 5
1 6

예제 출력 1

12

예제 입력 2

3 3
0 3
1 5
0 6

예제 출력 2

3

Solution

#include<stdio.h>

int main(void)
{
	int N, K, S, Y, total[2][6]={0, }, room=0;

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

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

	for(int i=0;i<6;i++)
		for(int j=0;j<2;j++)
			room+=total[j][i]/K+(total[j][i]%K!=0);

	printf("%d\n", room);
	return 0;
}

728x90

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

<백준 알고리즘> 2738번: 행렬 덧셈 (0)	2021.02.05
<백준 알고리즘> 5576번: 콘테스트 (0)	2021.02.04
<백준 알고리즘> 2846번: 오르막길 (0)	2021.02.04
<백준 알고리즘> 5598번: 카이사르 암호 (0)	2021.02.04
<백준 알고리즘> 10101번: 삼각형 외우기 (0)	2021.02.04