문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

예제 입력 1

4

예제 출력 1

5
더보기

Solution

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

int main(void)
{
	int **tile=malloc(2*sizeof(int *)), N;

	scanf("%d", &N);
	for(int i=0;i<2;i++)
		tile[i]=calloc(N+1,sizeof(int));

	tile[1][1]=tile[1][2]=1;
	tile[0][2]=1;
	for(int n=3;n<=N;n++)
	{
		tile[0][n]=(tile[0][n-2]+tile[1][n-2])%15746;
		tile[1][n]=(tile[0][n-1]+tile[1][n-1])%15746;
	}

	printf("%d\n", (tile[0][N]+tile[1][N])%15746);
	for(int i=0;i<2;i++)
		free(tile[i]);
	free(tile);
	return 0;
}
728x90

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

<백준 알고리즘> 10844번: 쉬운 계단 수  (0) 2021.02.21
<백준 알고리즘> 1149번: RGB거리  (0) 2021.02.21
<백준 알고리즘> 9184번: 신나는 함수 실행  (0) 2021.02.21
<백준 알고리즘> 10816번: 숫자 카드 2  (0) 2021.02.20
<백준 알고리즘> 2979번: 트럭 주차  (0) 2021.02.14

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
	1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
	w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
	w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
	w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

 

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

제한

  • -50 ≤ a, b, c ≤ 50

예제 입력 1

1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1

예제 출력 1

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1
더보기

Solution

#include<stdio.h>

int main(void)
{
	int w[21][21][21]={0, }, a, b, c;

	for(a=0;a<21;a++)
		for(b=0;b<21;b++)
			for(c=0;c<21;c++)
				if(a==0 || b==0 || c==0)
					w[a][b][c]=1;
				else if(a<b && b<c)
					w[a][b][c]=w[a][b][c-1]+w[a][b-1][c-1]-w[a][b-1][c];
				else
					w[a][b][c]=w[a-1][b][c]+w[a-1][b-1][c]+w[a-1][b][c-1]-w[a-1][b-1][c-1];

	scanf("%d %d %d", &a, &b, &c);

	while(a!=-1 || b!=-1 || c!=-1)
	{
		if(a<=0 || b<=0 || c<=0)
			printf("w(%d, %d, %d) = %d\n", a, b, c, 1);
		else if(a>20 || b>20 || c>20)
			printf("w(%d, %d, %d) = %d\n", a, b, c, w[20][20][20]);
		else
			printf("w(%d, %d, %d) = %d\n", a, b, c, w[a][b][c]);

		scanf("%d %d %d", &a, &b, &c);
	}

	return 0;
}
728x90

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

<백준 알고리즘> 1149번: RGB거리  (0) 2021.02.21
<백준 알고리즘> 1904번: 01타일  (0) 2021.02.21
<백준 알고리즘> 10816번: 숫자 카드 2  (0) 2021.02.20
<백준 알고리즘> 2979번: 트럭 주차  (0) 2021.02.14
<백준 알고리즘> 11727번: 2×n 타일링 2  (0) 2021.02.14

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 1

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1

3 0 0 1 2 0 0 2
더보기

Solution

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

int main(void)
{
	int N, M, *num=calloc(20000001,sizeof(int)), card;

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

	scanf("%d", &M);
	for(int m=0;m<M;m++)
	{
		scanf("%d", &card);
		printf("%d ", num[card+10000000]);
	}

	printf("\n");
	free(num);
	return 0;
}
728x90

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

<백준 알고리즘> 1904번: 01타일  (0) 2021.02.21
<백준 알고리즘> 9184번: 신나는 함수 실행  (0) 2021.02.21
<백준 알고리즘> 2979번: 트럭 주차  (0) 2021.02.14
<백준 알고리즘> 11727번: 2×n 타일링 2  (0) 2021.02.14
<백준 알고리즘> 2156번: 포도주 시식  (0) 2021.02.14

문제

상근이는 트럭을 총 세 대 가지고 있다. 오늘은 트럭을 주차하는데 비용이 얼마나 필요한지 알아보려고 한다.

상근이가 이용하는 주차장은 주차하는 트럭의 수에 따라서 주차 요금을 할인해 준다.

트럭을 한 대 주차할 때는 1분에 한 대당 A원을 내야 한다. 두 대를 주차할 때는 1분에 한 대당 B원, 세 대를 주차할 때는 1분에 한 대당 C원을 내야 한다.

A, B, C가 주어지고, 상근이의 트럭이 주차장에 주차된 시간이 주어졌을 때, 주차 요금으로 얼마를 내야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문제에서 설명한 주차 요금 A, B, C가 주어진다. (1 ≤ C ≤ B ≤ A ≤ 100)

다음 세 개 줄에는 두 정수가 주어진다. 이 정수는 상근이가 가지고 있는 트럭이 주차장에 도착한 시간과 주차장에서 떠난 시간이다. 도착한 시간은 항상 떠난 시간보다 앞선다. 입력으로 주어지는 시간은 1과 100사이 이다.

출력

첫째 줄에 상근이가 내야하는 주차 요금을 출력한다.

예제 입력 1

5 3 1
1 6
3 5
2 8

예제 출력 1

33
더보기

Solution

#include<stdio.h>

int main(void)
{
	int A, B, C, time[101]={0, }, start, end, price=0;

	scanf("%d %d %d", &A, &B, &C);

	for(int i=0;i<3;i++)
	{
		scanf("%d %d", &start, &end);

		for(int t=start;t<end;t++)
			time[t]++;
	}

	for(int i=1;i<101;i++)
		price+=time[i]==1?A:time[i]==2?2*B:time[i]==3?3*C:0;

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

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

<백준 알고리즘> 9184번: 신나는 함수 실행  (0) 2021.02.21
<백준 알고리즘> 10816번: 숫자 카드 2  (0) 2021.02.20
<백준 알고리즘> 11727번: 2×n 타일링 2  (0) 2021.02.14
<백준 알고리즘> 2156번: 포도주 시식  (0) 2021.02.14
<백준 알고리즘> 2193번: 이친수  (0) 2021.02.13

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

예제 입력 3

12

예제 출력 3

2731
더보기

Solution

#include<stdio.h>

int main(void)
{
	int n, rectangle[1001]={0,1,3,0, };

	scanf("%d", &n);

	for(int i=3;i<=n;i++)
		rectangle[i]=(rectangle[i-1]+2*rectangle[i-2])%10007;

	printf("%d\n", rectangle[n]);
	return 0;
}
728x90

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

<백준 알고리즘> 10816번: 숫자 카드 2  (0) 2021.02.20
<백준 알고리즘> 2979번: 트럭 주차  (0) 2021.02.14
<백준 알고리즘> 2156번: 포도주 시식  (0) 2021.02.14
<백준 알고리즘> 2193번: 이친수  (0) 2021.02.13
<백준 알고리즘> 1747번: 소수&팰린드롬  (0) 2021.02.09

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

  1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
  2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

예제 입력 1

6
6
10
13
9
8
1

예제 출력 1

33
더보기

Solution

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

int main(void)
{
	int n, *wine=NULL, **maxwine=NULL, max=0;

	scanf("%d", &n);
	wine=(int *)malloc(n*sizeof(int));
	maxwine=(int **)malloc(n*sizeof(int *));
	for(int i=0;i<n;i++)
		maxwine[i]=(int *)calloc(3,sizeof(int));

	for(int i=0;i<n;i++)
	{
		scanf("%d", &wine[i]);

		if(i>0)
		{
			maxwine[i][0]=maxwine[i-1][0]>=maxwine[i-1][1]&&maxwine[i-1][0]>=maxwine[i-1][2]?maxwine[i-1][0]:maxwine[i-1][1]>=maxwine[i-1][0]&&maxwine[i-1][1]>=maxwine[i-1][2]?maxwine[i-1][1]:maxwine[i-1][2];
			maxwine[i][1]=maxwine[i-1][0]+wine[i];
			maxwine[i][2]=maxwine[i-1][1]+wine[i];
		}
		else
			maxwine[0][1]=wine[0];
	}
	max=maxwine[n-1][0]>max?maxwine[n-1][0]:max;
	max=maxwine[n-1][1]>max?maxwine[n-1][1]:max;
	max=maxwine[n-1][2]>max?maxwine[n-1][2]:max;

	printf("%d\n", max);
	for(int i=0;i<n;i++)
		free(maxwine[i]);
	free(maxwine);
	free(wine);
	return 0;
}
728x90

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

<백준 알고리즘> 2979번: 트럭 주차  (0) 2021.02.14
<백준 알고리즘> 11727번: 2×n 타일링 2  (0) 2021.02.14
<백준 알고리즘> 2193번: 이친수  (0) 2021.02.13
<백준 알고리즘> 1747번: 소수&팰린드롬  (0) 2021.02.09
<백준 알고리즘> 11051번: 이항 계수 2  (0) 2021.02.08

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

  1. 이친수는 0으로 시작하지 않는다.
  2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

예제 입력 1

3

예제 출력 1

2
더보기

Solution

#include<stdio.h>

int main(void)
{
	long int pinary[2][90]={0, };
	int N;

	scanf("%d", &N);

	pinary[1][0]=1;
	for(int n=1;n<N;n++)
	{
		pinary[1][n]=pinary[0][n-1];
		pinary[0][n]=pinary[0][n-1]+pinary[1][n-1];
	}

	printf("%ld\n", pinary[0][N-1]+pinary[1][N-1]);
	return 0;
}
728x90

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

<백준 알고리즘> 11727번: 2×n 타일링 2  (0) 2021.02.14
<백준 알고리즘> 2156번: 포도주 시식  (0) 2021.02.14
<백준 알고리즘> 1747번: 소수&팰린드롬  (0) 2021.02.09
<백준 알고리즘> 11051번: 이항 계수 2  (0) 2021.02.08
<백준 알고리즘> 2579번: 계단 오르기  (0) 2021.02.08

문제

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

예제 입력 1

31

예제 출력 1

101
더보기

Solution

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

bool isPrime(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;
}

bool isPalindrome(char *str,int length)
{
	for(int i=0;i<length/2;i++)
		if(str[i]!=str[length-1-i])
			return false;
	return true;
}

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

	scanf("%d", &N);
	sprintf(str,"%d",N);

	while(!isPrime(N)||!isPalindrome(str,strlen(str)))
		sprintf(str,"%d",++N);

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

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

<백준 알고리즘> 2156번: 포도주 시식  (0) 2021.02.14
<백준 알고리즘> 2193번: 이친수  (0) 2021.02.13
<백준 알고리즘> 11051번: 이항 계수 2  (0) 2021.02.08
<백준 알고리즘> 2579번: 계단 오르기  (0) 2021.02.08
<백준 알고리즘> 2947번: 나무 조각  (0) 2021.02.05

+ Recent posts

티스토리툴바