okayoki

#문제

https://www.acmicpc.net/problem/10844

#작성 코드

#include <iostream>
using namespace std;

int mod = 1000000000;
int N;
int memo[101][10]={ 0,};

int stair(int n){
	// 1자리수 계단수는 각각 1개이다. 
	for(int i=1; i<10; i++)
		memo[1][i] = 1;
	
	// i자리수, j로 끝나는 계단수
	// n자리수까지 계산한다.	
	for(int i=2; i<=n; i++){
		for(int j=0; j<10; j++){
			// 이후에 0이 될 수 있는 경우는 이전에 1이었던 경우 뿐 
			if( j==0 ){
				memo[i][0] = memo[i-1][1]%mod;
			}
			// 이후에 9가 될 수 있는 경우는 이전에 8이었던 경우 뿐 
			else if( j==9 ){
				memo[i][j] = memo[i-1][8]%mod;
			}
			// 나머지 경우는 j의 이전, 이후 수 모두에 대해 가능하다. 
			else{
				memo[i][j] = (memo[i-1][j-1]+memo[i-1][j+1])%mod;
			}
		}
	}
	
	// n자리수의 계단수. 끝 숫자가 0~9인경우 모두의 합을 구한다. 
	int sum=0;
	for(int i=0; i<10; i++){
		sum = (sum+memo[n][i])%mod;
	}
	return sum;
}
int main(){
	cin>>N;
	cout<<stair(N);
	return 0;
} 

##

#문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

#작성 코드

1. DFS 사용

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int com, net, cnt=0;
// 컴퓨터의 수, 연결 쌍의 수, 1번 컴퓨터를 통해 감염되는 컴퓨터 수 
vector<int> node[101];		// n번 컴퓨터(1~100)의 연결상태 저장 
bool visit[101]={ false,};	// n번(1~100) 컴퓨터 방문여부 

void dfs(int s){
	visit[s]=true;		// 매개변수로 주어진 컴퓨터 방문처리 
	
	// s에 연결되어있는 컴퓨터 중 방문하지 않은 컴퓨터 방문
	for(vector<int>::iterator i=node[s].begin(); i<node[s].end(); i++){
		if( visit[*i]==true) continue;
		visit[*i] = true;
		cnt++;
		dfs(*i);		// 연결되어있는 컴퓨터에 연결된 컴퓨터 재귀적으로 방문 
	}
}

int main(){
	cin>>com>>net;
	
	// 컴퓨터를 잇는 네트워크 쌍을 입력받는다. 
	for(int i=1; i<=net; i++){
		int a, b;
		cin>>a>>b;
		node[a].push_back(b);
		node[b].push_back(a);
	}
	
	// 각 컴퓨터에 연결된 네트워크를 순서대로 정렬 
	for(int i=1; i<=com; i++)
		sort(node[i].begin(), node[i].end());
		
	dfs(1);	// 1번 컴퓨터에서부터 탐색을 시작한다. 
	cout<<cnt;
	return 0;
}

2. BFS 사용

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int com, net, cnt=0;
// 컴퓨터의 수, 연결 쌍의 수, 1번 컴퓨터를 통해 감염되는 컴퓨터 수 
queue<int> q;		// bfs에 사용 
vector<int> node[101];		// n번 컴퓨터(1~100)의 연결상태 저장 
bool visit[101]={ false,};	// n번(1~100) 컴퓨터 방문여부 

void bfs(int start){
	// 탐색을 시작할 컴퓨터(1번) 방문처리 
	q.push(start);
	visit[start]=true;
	
	while(!q.empty()){
		int x = q.front();
		q.pop();
		// x번 컴퓨터에 연결되어있는 자식들 중 방문하지 않은것에 하나씩 방문 
		for(int i=0; i<node[x].size(); i++){
			int tmp = node[x][i];
			if( visit[tmp]==true ) continue;
			visit[tmp]=true;
			cnt++;
			q.push(tmp);
		}
	}
}

int main(){
	cin>>com>>net;
	
	// 컴퓨터를 잇는 네트워크 쌍을 입력받는다. 
	for(int i=1; i<=net; i++){
		int a, b;
		cin>>a>>b;
		node[a].push_back(b);
		node[b].push_back(a);
	}
	
	// 각 컴퓨터에 연결된 네트워크를 순서대로 정렬 
	for(int i=1; i<=com; i++)
		sort(node[i].begin(), node[i].end());
		
	bfs(1);	// 1번 컴퓨터에서부터 탐색을 시작한다. 
	cout<<cnt;
	return 0;
}

##

분명 엊그제 풀었을 때는 몇 번이나 틀렸었는데....

191203 - 복습하면서 주석 추가.

#문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

#작성 코드

#include <iostream>
using namespace std;

int cnt=0;
int memo[1000001];

int op(int n){
	memo[1] = 0;
	memo[2] = 1;
	memo[3] = 1;
	for(int i=4; i<=n; i++){
		memo[i] = memo[i-1]+1;
		if( i%2 == 0 ){
			memo[i] = min( memo[i/2]+1, memo[i] );
		}
		if( i%3 == 0 ){
			memo[i] = min( memo[i/3]+1, memo[i] );
		}
		// 1을 더해서, 2를 곱해서, 3을 곱해서 i가 되는 경우 중 연산 최솟값 
	}
	return memo[n];
}
int main(){
	int N;
	cin>>N;
	cout<<op(N);
	return 0;
}

##

입력받을 수 N은 최대 10^6이 될 수 있으므로,

어느 수 i를 만들 때까지 수행된 연산 횟수를 저장할 배열 memo[10^6+1]을 선언한다.

1에서부터 출발하여 N을 만드는 연산 횟수는

   1. 1을 더해서 n-1에서 n만들기

   2. 2를 곱해서 n/2 에서 n만들기 @n%2==0인 경우.

   3. 3을 곱해서 n/3에서 n만들기 @n%3==0인 경우.

이 경우들 중 연산 횟수가 최소가 되는 경우를 memo[n]에 저장한다.

#191216 review

위의 방식은 1을 n으로 만드는 방식이다.

문제 형식과 같이 n을 1로 만드는 방식으로 문제를 풀어보고싶었다.

for문 내부의 i/3, i/2, i-1 케이스 연산은 순서에 관계없다.

위의 코드와 다르게 꼭 설정해야 하는 것은 make1_d[n] = 0을 제외한 모든 인덱스 값을 아주 큰 수로 초기화시켜야 한다는 것이다.

min값을 계산할 때 초기값이 0이라면 절대 업데이트 되지 않는다.

TOP-DOWN 방식

N을 1로 만드는 최소 횟수 = f(N)이라고 하면

만약 N이 1인 경우에는 f(N)=0을 리턴해버린다.

dp(N)이 이미 계산되었다면(dp는 연산의 최소횟수가 될 수 없는 -1로 초기화해둬야한다.) dp(N)을 리턴한다.

새로 dp(N)을 계산해야 하는 경우...

dp(N) = f(N) = min( f(N/3)+1, f(N/2)+1, f(N-1)+1 ) 이 된다. return dp(N)

BOTTOM-UP 방식

N=1 -> F(N)=0

N=2 -> F(N)=1

N=3 -> F(N)=1

N=4 -> F(N) = min( F(N-1)+1, F(N/2)+1 )          4는 3의 배수가 아니므로...

...

F(N) = F(N-1)+1

만약 N이 2의 배수이면 F(N) = min( F(N),  F(N/2)+1 )

만약 N이 3의 배수이면 F(N) = min( F(N), F(N/3)+1 ) 으로 갱신해준다.

#문제

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

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

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

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

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

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

입력

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

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

출력

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

#작성 코드

#include <iostream>
using namespace std;

int n;
int arr[301];	// 계단에 쓰여 있는 점수 저장. 인덱스 1~300사용 
int sums[301][3];	// [i][1]은 이전에 1칸 이동, [i][2]는 이전에 2칸 이동 

int stair(int n){
	// 첫번째 계단으로 이동하는것은 1칸을 이동하는것, 2칸을 이동하는 것 동일하다. 
	sums[1][1]=sums[1][2] =arr[1];
	for(int i=2; i<=n; i++){
		// 이전에 1칸 이동-> 무조건 2칸 이동해야함 
		sums[i][1] = sums[i-1][2]+arr[i];
		// 이전에 2칸 이동 -> 1칸 이동, 2칸 이동 모두 가능. 최댓값되는조건으로 진행 
		sums[i][2] = max( sums[i-2][1], sums[i-2][2] ) + arr[i];
	}
	return max(sums[n][1], sums[n][2]); 
}
int main(){
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>arr[i];
	}
	cout<<stair(n)<<'\n';
	return 0;
} 

##

왜 이전에 1칸을 이동한 후에는 무조건 2칸만 이동해야하는지 이해하기 위한 노트.

#191216 review

#문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다.

#작성 코드

#include <iostream>
using namespace std;
 
int nums[100001];
int main(){
	int k;	// 입력받을 정수의 개수 
	int idx=-1;
	cin>>k;
	
	// k개의 줄에 정수를 1개씩 입력받음 
	for(int i=0; i<k; i++){
		int tmp;
		cin>>tmp;
		// 입력받은 수가 0이 아니면 해당 수를 쓴다. 
		if( tmp!=0 ){
			idx++;
			nums[idx]=tmp;
			continue;
		}
		// 입력받은 수가 0이면 가장 최근에 쓴 수를 지운다. 
		else{
			idx--;
			continue;
		}
	}
	
	// 최종적으로 남은 수들의 합을 출력. 
	int sum=0;
	for(int i=0; i<=idx; i++){
		sum+=nums[i];
	}
	cout<<sum<<'\n';
	return 0;
}

##

#문제

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

입력

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

출력

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

#작성 코드

#include <cstdio>

long long int memo[1000001][2];

long long int tile(int x){
	memo[0][0] = 0;
	memo[1][0] = 2;
	memo[2][0] = 7;
	memo[2][1] = 1;
	for(int i=3; i<=x; i++){
		// 2*{tile(i-3) + tile(i-4) + ... + tile(0)}부분을 빠르게 계산하기 위해 저장. 
		memo[i][1] = (memo[i-1][1]+memo[i-3][0])%1000000007;
		memo[i][0] = (3*memo[i-2][0]+2*memo[i-1][0]+2*memo[i][1])%1000000007;
	}
	return memo[x][0];
} 

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

##