코딩 초보 삐리리뽀옹이 나가신다

/*
	이름 궁합
	단순 구현
*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solve(vector<int> nums){
	if(nums.size() == 2)
		return nums;
	vector<int> answer;
	for(int i=0;i<(int)nums.size()-1;i++)
		answer.push_back((nums[i]+nums[i+1])%10);

	return solve(answer);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	vector<int> cnt = {3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1};

	string jm, jh;
	cin >> jm >> jh;
	
	vector<int> nums;
	for(int i=0;i<jm.length();i++){
		nums.push_back(cnt[jm[i] - 'A']);
		nums.push_back(cnt[jh[i] - 'A']);
	}
	vector<int> result = solve(nums);
	for(auto r : result)
		cout << r;
	cout << endl;

	return 0;
}

/*
	파이프 옮기기 1
	알고리즘
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int N, answer = 0;
	cin >> N;

	vector<vector<int>> house(N+1, vector<int>(N+1));
	/*
		0 - 가로
		1 - 세로
		2 - 대각선
	*/
	vector<vector<vector<int>>> dp(3,vector<vector<int>>(N+1, vector<int>(N+1, 0)));

	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			cin >> house[i][j];

	for(int i=2;i<=N && !house[1][i];i++)
		dp[0][1][i] = 1;

	for(int i=2;i<=N;i++){
		for(int j=2;j<=N;j++){
			if(!house[i][j]){
				dp[0][i][j] = dp[0][i][j-1] + dp[2][i][j-1];
				dp[1][i][j] = dp[1][i-1][j] + dp[2][i-1][j];
				if(!house[i-1][j] && !house[i][j-1]){
					dp[2][i][j] = dp[0][i-1][j-1] + dp[1][i-1][j-1] + dp[2][i-1][j-1];
				}
			}
		}
	}
	for(int i=0;i<3;i++)
		answer += dp[i][N][N];
	
	cout << answer << endl;

	return 0;
}

/*
	1학년
	DP
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	const int maxSum = 20;
	int N;
	cin >> N;

	vector<int> nums(N);

	for(int i=0;i<N;i++)
		cin >> nums[i];

	vector<vector<long long>> DP(21, vector<long long>(N, 0));
	
	DP[nums[0]][0] = 1;

	for(int i=1;i<N-1;i++){
		for(int j=0;j<=maxSum;j++){
			if(j-nums[i] >= 0)
				DP[j][i] += DP[j-nums[i]][i-1];
			if(j+nums[i] <= maxSum)
				DP[j][i] += DP[j+nums[i]][i-1];
		}
	}

	cout << DP[nums[N-1]][N-2] << "\n";

	return 0;
}

/*
	알고스팟
    BFS, Priority queue
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int dx[4] = {-1, 1, 0, 0};
	int dy[4] = {0, 0, -1, 1};

	int N, M, answer = -1;
	cin >> M >> N;
	
	vector<vector<char>> miro(N+1, vector<char>(M+1));
	vector<vector<bool>> visited(N+1, vector<bool>(M+1, false));

	priority_queue<tuple<int, int, int>> pq;

	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
			cin >> miro[i][j];

	pq.push({0, 1, 1});
	visited[1][1] = true;

	while(!pq.empty()){
		int wall = get<0>(pq.top());
		int x = get<1>(pq.top());
		int y = get<2>(pq.top());
		pq.pop();
		
		if(x==N && y==M){
			answer = -wall;
			break;
		}
		for(int i=0;i<4;i++){
			int nx = x + dx[i];
			int ny = y + dy[i];

			if(nx<=0 || nx>N || ny<=0 || ny>M)
				continue;
			if(visited[nx][ny])
				continue;
			
			visited[nx][ny] = true;
			pq.push({(miro[nx][ny]=='1'? wall-1 : wall), nx, ny});
		}
	}
	
	cout << answer << endl;

	return 0;
}

/*
	돌 게임
	DP
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;
	
	vector<bool> dp(N+1);

	dp[1] = true;
	dp[2] = false;

	for(int i=3;i<=N;i++)
		dp[i] = dp[i-2];
		 
	cout << (dp[N]? "SK\n" : "CY\n");

	return 0;
}

/*
	토마토(3차원)
	BFS
	난이도 
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int answer = 0;
	int M, N, H;
	cin >> M >> N >> H;

	vector<vector<vector<int>>> box(H, vector<vector<int>>(N, vector<int>(M, 0)));
	queue<tuple<int, int, int>> q;
	int dx[6] = {-1, 1, 0, 0, 0, 0};
	int dy[6] = {0, 0, -1, 1, 0, 0};
	int dz[6] = {0, 0, 0, 0, -1, 1};
	
	//입력
	for(int i=0;i<H;i++){
		for(int j=0;j<N;j++){
			for(int k=0;k<M;k++){
				cin >> box[i][j][k];
				if(box[i][j][k] == 1)
					q.push({i, j, k});
			}
		}
	}
	//BFS 시작
	while(!q.empty()){
		int z = get<0>(q.front());
		int x = get<1>(q.front());
		int y = get<2>(q.front());
		q.pop();

		for(int i=0;i<6;i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];

			if(nx<0 || nx>=N || ny<0 || ny>=M || nz<0 || nz>=H)
				continue;
			if(box[nz][nx][ny] != 0)
				continue;
			box[nz][nx][ny] = box[z][x][y] + 1;
			q.push({nz, nx, ny});
		}
	}

	//다 익을 수 없는 경우 체크, 토마토가 익는 데 걸리는 최대 시간 찾기
	for(int i=0;i<H;i++){
		for(int j=0;j<N;j++){
			for(int k=0;k<M;k++){	
				if(box[i][j][k] == 0){
					cout << "-1\n";
					return 0;
				}
				answer = max(answer, box[i][j][k]);
			}
		}
	}
	
	//1부터 셌으니까 -1 해서 출력
	cout << answer - 1 << "\n";

	return 0;
}

/*
	바이러스
	DFS
	난이도
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<vector<int>> links; // 컴퓨터 간 연결 정보
vector<bool> visited; // 방문 확인

int dfs(int cur){
	if(visited[cur])
		return 0;
	visited[cur] = true;
	int cnt = 1; // 자신이 감염되므로 1부터 시작한다.
	for(auto next : links[cur])
		cnt += dfs(next);
	return cnt;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;

	links.reserve(N+1);
	visited.reserve(N+1);

	fill(visited.begin(), visited.end(), false);
	
	for(int i=0;i<M;i++){
		int a, b;
		cin >> a >> b;
		links[a].push_back(b);
		links[b].push_back(a);
	}

	cout << dfs(1) - 1 << endl; // 1번 노드 제외

	return 0;
}