okayoki

#문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

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

출력

첫째 줄에 경우의 수를 출력한다.

#작성 코드

#include <cstdio>

int memo[31];

int tile(int x){
	if(x==0) return 1;	// 아무 것도 놓지 않는 것은 한가지 
	if(x==1) return 0;
	if(x==2) return 3;
	if( memo[x]!=0 ) return memo[x];
	int result = tile(x-2)*3;
	for(int i=4; i<=x; i+=2){
		result+=2*tile(x-i);
	}
	return memo[x]=result;
}

int main()
{
	int n;
	scanf("%d", &n);
	printf("%d\n", tile(n));
	return 0;
}

##

n이 홀수일 때는 절대 타일을 채울 수 없다.

n이 짝수일 때

-> 0일때는 1가지. 아무것도 놓지 않는 것도 한가지의 방법이다.

-> 2일때는 3가지.

-> 4일때는 2일때의 3가지에 2가지를 추가하게된다.

     ex)

+) N이 조금 더 큰 수일 경우에 2차원 dp를 사용하면 +2*tile(n-4)+2*tile(n-6)+... +2*tile(0)의 계산을 더 빠르게 수행할 수 있지 않을까 해서 2차원 dp를 사용해서도 풀어보았다.

#include <iostream>

int memo[31][2];
// memo[n][0]에는 3xn타일을 칠하는 경우의 수 저장.
// memo[n][1]에는 3x(0) ~ 3x(n-2)타일을 칠하는 경우의 수의 합 저장.

int tile(int x){
	memo[0][0] = 1;
	memo[1][0] = 0;
	memo[2][0] = 3;
	memo[2][1] = 1;
	if( x%2!= 0) return 0;
	for(int i=4; i<=x; i+=2){
		memo[i][1] = memo[i-2][1] + memo[i-2][0];
		memo[i][0] = 3*memo[i-2][0] + 2*memo[i-2][1];	
	}
	return memo[x][0];
}

int main(){
	int n;
	std::cin>>n;
	std::cout<<tile(n)<<'\n';
	return 0;
}

note

더보기

#문제

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

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

입력

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

출력

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

#작성 코드

#include <cstdio>

int memo[1001];
int dp(int x){
	if( x==1 ) return 1;
	if( x==2 ) return 3;
	if( memo[x]!=0 ) return memo[x];
	return memo[x] = (dp(x-1) + 2*dp(x-2))%10007;	
}

int main(){
	int n;
	scanf("%d", &n);
	printf("%d\n", dp(n));
	return 0;
}

##

#문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

#작성 코드

#include <cstdio>

int d[1001];

int dp(int x){
	if (x==1) return 1;
	if (x==2) return 2;
	if( d[x]!=0 ) return d[x];
	return d[x] = (dp(x-1)+dp(x-2))%10007;
}

int main(){
	int n;
	scanf("%d", &n);
	printf("%d\n", dp(n));
	return 0;
}

##

#문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.

• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

• size: 스택에 들어있는 정수의 개수를 출력한다.

• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.

• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

#작성 코드

#include <iostream>
#include <cstdio>
#define STACK_SIZE 10000
using namespace std;

int N;	//명령의 개수 
typedef class stack{
	public:
		// 정수 x를 스택에 넣는 연산이다. 
		void push(int x){
			if(s_top>STACK_SIZE){
				return;
			}
			s_top++;
			s[s_top] = x;
		}
		// 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다.
		// 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 
		void pop(){
			if( s_top<0 ){
				printf("-1\n");
				return;
			}
			printf("%d\n", s[s_top]);
			s_top--;
		}
		// 스택에 들어있는 정수의 개수를 출력한다. 
		void size(){
			printf("%d\n", s_top+1); 
		}
		// 스택이 비어있으면 1, 아니면 0을 출력한다. 
		void empty(){
			if( s_top<0 ){
				printf("1\n");
			}
			else printf("0\n");
		}
		// 스택의 가장 위에 있는 정수를 출력한다.
		// 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 
		void top(){
			if( s_top<0 ){
				printf("-1\n");
			}
			else printf("%d\n", s[s_top]);
		}
	private:
		int s_top=-1;
		int s[STACK_SIZE]; 
}stack;

int main(){
	stack s;
	cin>>N;
	string command;
	int x;
	for(int i=0; i<N; i++){
		cin>>command;
		if( "push" == command ){
			cin>>x;
			s.push(x);
		}
		else if("pop"==command){
			s.pop();
		}else if("size"==command){
			s.size();
		}else if("empty"==command){
			s.empty();
		}else if("top"==command){
			s.top();
		}
	}
	return 0;
} 

##

#문제

     7

    3 8

   8 1 0

  2 7 4 4

 4 5 2 6 5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

#작성 코드

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int n;
int **tri;
int **triSum;

int main(){
	// 정수 삼각형의 크기 입력 
	scanf("%d", &n);
	// 정수 삼각형 할당 인덱스 1에서부터 사용. i 층에는 i개만큼 배열 할당 
	tri = new int*[n+1];
	for(int i=1; i<=n+1; i++){
		tri[i] = new int[i];
	}
	// 정수 삼각형의 합을 저장할 이차원 배열 할당.
	// triSum[i][j]에는 i층 j번째 원소까지의 합 중 가장 합이 큰 경로의 합 저장 
	triSum = new int*[n+1];
	for(int i=1; i<=n+1; i++){
		triSum[i] = new int[i];
	}
	
	// 정수 삼각형 입력
	for(int i=1; i<=n; i++){
		for(int j=1; j<=i; j++){
			scanf("%d", &tri[i][j]);
		}
	}
	
	// 첫 번째 합 = 첫 번째 원소 
	triSum[1][1] = tri[1][1];
	// 두 번째 층부터 시작 
	for(int i=2; i<=n; i++){
		for(int j=1; j<=i; j++){
			// 해당 층의 첫 원소일 때  
			if( j==1 ){
				triSum[i][j] = triSum[i-1][j]+tri[i][j];
			}
			// 해당 층의 마지막 원소일 때 
			else if( i==j ){
				triSum[i][j] = triSum[i-1][j-1]+tri[i][j];
			}
			// 안쪽에 있는 원소라면 이전 층의 j-1, j번째까지의 triSum 중에서
			// 큰 쪽을 선택하여 이번 층의 원소를 더한다. 
			else{
				triSum[i][j] = max(triSum[i-1][j-1], triSum[i-1][j])+tri[i][j];
			}
		}
	}
	int result=0;
	for(int i=1; i<=n; i++){
		result = max(result, triSum[n][i]);
	}
	printf("%d", result);
	return 0;
} 

##

#문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로, 초록으로, 파랑으로 칠하는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

#작성 코드

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

int N;
int house[1001][3];
int tmp[3];		// 현재까지 선택의 최솟값들 저장. 
int choice[3];

int answer(){
	tmp[0] = house[1][0];	// 첫번째 집에서 빨강 선택 
	tmp[1] = house[1][1];	// 첫번째 집에서 초록 선택 
	tmp[2] = house[1][2];	// 첫번째 집에서 파랑 선택 
	
	// 두번째 집부터 마지막 집까지 순회 
	for(int num=2; num<=N; num++){
		// 새 집에서 빨강 선택 <- 이전 집에서 초록, 파랑 선택한 결과 중 작은것 
		choice[0] = house[num][0]+min(tmp[1], tmp[2]); 
		// 새 집에서 초록 선택 <- 이전 집에서 빨강, 파랑 선택한 결과 중 작은것
		choice[1] = house[num][1]+min(tmp[0], tmp[2]);
		// 새 집에서 파랑 선택 <- 이전 집에서 빨강, 초록 선택한 결과 중 작은것
		choice[2] = house[num][2]+min(tmp[0], tmp[1]);
		
		// 각 결과들을 재사용할 수 있도록 저장. 
		tmp[0] = choice[0];
		tmp[1] = choice[1];
		tmp[2] = choice[2];
	}
	
	// 모든 집을 순회한 후, 제일 마지막 집에서 빨강, 초록, 파랑 선택한 누적 결과 중 최솟값 리턴 
	return min(min(tmp[0], tmp[1]), tmp[2]);
}

int main(){
	scanf("%d", &N);
	for(int i=1; i<=N; i++){
		// 각 집을 빨강, 초록, 파랑으로 칠하는 비용 
		scanf("%d %d %d", &house[i][0], &house[i][1], &house[i][2]);
	}
	printf("%d\n", answer());
	return 0;
}

##

집의 수 N은 최대 1000, 각 집에 칠할 수 있는 R, G, B 비용 ->int  house[1001][3]배열을 선언

#191216 review

아래의 코드처럼 1~i번째 집을 칠하는 비용을 저장하는 배열을 추가 선언하여도 메모리 상에서 크게 차이나지않는다.