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

첫 번째 방법

//BFS 탐색을 2 depth까지 하는 비효율적인 방식의 첫 시도
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

bool isFar(const int boardSize, vector<string> place, vector<vector<int>> &visited){
    const vector<int> dx = {-1, 1, 0, 0};
    const vector<int> dy = {0, 0, -1, 1};
    
    queue<tuple<int, int, int, int>> q;
        
    for(int i=0;i<boardSize;i++){
        for(int j=0;j<boardSize;j++){
            if(place[i][j] == 'P')
				q.push({i, j, 0, q.size()});
        }
    }
	while(!q.empty()){
      	int x = get<0>(q.front());
        int y = get<1>(q.front());
        int c = get<2>(q.front()); // 거리
        int v = get<3>(q.front()); // 탐색 중인 면접자의 index
        q.pop();
        
        visited[x][y] = v;
        
        for(int d=0;d<4;d++){
            int nx = x + dx[d];
            int ny = y + dy[d];
            int nc = c + 1;
                
            if(nx<0 || nx>=boardSize || ny<0 || ny>=boardSize
            	|| visited[nx][ny]==visited[x][y] // 탐색 중인 면접자가 방문한 적이 있다면 continue
               	|| place[nx][ny]=='X' // 파티션이면 continue
              	|| nc>2) // 다음에 갈 자리가 맨해튼 거리 2 초과면 continue
            	continue;
            
            if(place[nx][ny] == 'P')
                return false;
            q.push({nx, ny, nc, v});
        }
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
	vector<int> answer;
    const int boardSize = 5;
	vector<vector<int>> visited(boardSize, vector<int>(boardSize, -1));
	
    for(auto place : places)
		answer.push_back(isFar(boardSize, place, visited));
    
	return answer;
}

두 번째 방법

//1 depth BFS 탐색을 통한 효율적인 방법
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

bool isFar(const int boardSize, vector<string> place){
    const vector<int> di = {-1, 1, 0, 0};
    const vector<int> dj = {0, 0, -1, 1};
    
    vector<vector<bool>> visited(boardSize, vector<bool>(boardSize, false));
        
    for(int i=0;i<boardSize;i++){
        for(int j=0;j<boardSize;j++){
            if(place[i][j] == 'P'){
                visited[i][j] = true;
            	for(int d=0;d<4;d++){
                    int ni = i + di[d];
            		int nj = j + dj[d];
                    if(ni<0 || ni>=boardSize || nj<0 || nj>=boardSize || place[ni][nj]=='X')
                        continue;
                    if(visited[ni][nj])
                        return false;
                    visited[ni][nj] = true;
                }    
            }
        }
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
	vector<int> answer;
    const int boardSize = 5;
	
    for(auto place : places)
		answer.push_back(isFar(boardSize, place));
    
	return answer;
}

//재귀 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int N, M, K, answer = -1;
vector<string> lamp(50);

void reverseCol(int colIdx){
	//colIdx 열 램프 뒤집기
	for(int i=0;i<N;i++)
		lamp[i][colIdx] = (lamp[i][colIdx] == '0'? '1' : '0');
}

int countRow(int colIdx){
	//colIdx까지 몇 개의 램프가 켜져있는지 확인
	if(colIdx == 0)
		return 0;
	int i, j, answer = 0;
	for(i=0;i<N;i++){
		for(j=0;j<colIdx;j++){
			if(lamp[i][j] == '0')
				break;
		}
		if(j == colIdx)
			answer++;
	}
	return answer;
}

/*
	재귀 접근
	@colIdx 열 번호
	@changeCount 램프 열을 켜고 끌 수 있는 남은 횟수
*/
void solve(int colIdx, int changeCount){
	if(colIdx == M){
		//마지막 열일 경우
		if((K - changeCount)%2 == 0)
			//램프를 켜고 끌 수 있는 남은 횟수가 짝수일 경우에만 업데이트
			answer = max(answer, countRow(M));
		return;
	}
	
	//앞서 구한 최대로 켤 수 있는 램프 행의 수보다 켜져있는 램프의 수가 적으면 더 돌리지 않음
	if(countRow(colIdx + 1) > answer)
		solve(colIdx + 1, changeCount);

	reverseCol(colIdx);//뒤집기
	if(countRow(colIdx + 1) > answer && changeCount < K)
		//앞서 구한 최대로 켤 수 있는 램프 행의 수보다 켜져있는 램프 행의 수가 적으면 더 돌리지 않음
		solve(colIdx + 1, changeCount + 1);
	reverseCol(colIdx);//다시 뒤집기
}

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

	cin >> N >> M;
	for(int i=0;i<N;i++)
		cin >> lamp[i];
	cin >> K;
	
	solve(0, 0);

	cout << answer << endl;

	return 0;
}

//패턴과 맵을 이용한 풀이
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

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

	int N, M, K, answer = 0;
	cin >> N >> M;
	string lamp;
	//램프 행, 개수
	map<string, int> lampMap;

	for(int i=0;i<N;i++){
		cin >> lamp;
		//램프 맵에 카운트 증가
		lampMap[lamp] += 1;
	}
	cin >> K;

	for(auto x : lampMap){
		string row = x.first;
		int val	= x.second;
		//행에 있는 0의 개수
		int zeroCnt = count(row.begin(), row.end(), '0');
		
		//행에 있는 0을 모두 켰을 때 램프 열을 뒤집을 남은 횟수가 짝수여야 함.
		if(zeroCnt <= K && (K - zeroCnt)%2 == 0)
			answer = max(answer, val);
	}

	cout << answer << endl;

	return 0;
}

/*
	앱
	DP
    1차원 배열을 사용한 풀이
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

#define N_MAX 100
#define C_MAX 100
#define M_MAX 10000000

using namespace std;

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

	int N, M, maxCost, answer;
	vector<int> A(N_MAX, 0), C(N_MAX, 0);
	vector<int> dp(N_MAX*C_MAX + 1, 0);

	cin >> N >> M;
	
	for(int i=0;i<N;i++) cin >> A[i];
	for(int i=0;i<N;i++) cin >> C[i];
	
	maxCost = accumulate(C.begin(), C.end(), 0);
	
	for(int i=0;i<N;i++)
		for(int j=maxCost;j>=C[i];j--)
			dp[j] = max(dp[j], dp[j - C[i]] + A[i]);

	for(answer=0;answer<maxCost && dp[answer]<M;answer++);
	cout << answer << "\n";
}

#include <iostream>
#include <vector>
#include <algorithm>

#define N_GEAR 4
#define N_WHEEL 8

using namespace std;


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int K, gear_idx, direction, answer = 0;
	vector<vector<bool>> gear(N_GEAR+1, vector<bool>(N_WHEEL, false));
	string input;
	for(int i=1;i<=N_GEAR;i++){
		cin >> input;
		for(int j=0;j<N_WHEEL;j++){
			gear[i][j] = input[j]=='0'? 0 : 1;
		}
	}

	cin >> K;
	vector<bool> diff(5, false);

	while(K--){
		cin >> gear_idx >> direction;
		
		fill(diff.begin(), diff.end(), false);
	
		int left_direction = -direction;
		int right_direction = -direction;

		for(int i=gear_idx+1;i<=N_GEAR;i++)
			diff[i] = gear[i][6] != gear[i-1][2];

		for(int i=gear_idx-1;i>0;i--)
			diff[i] = gear[i][2] != gear[i+1][6];
	
		rotate(gear[gear_idx].begin(), (direction==1? gear[gear_idx].end() - 1 : gear[gear_idx].begin() + 1), gear[gear_idx].end());

		for(int i=gear_idx+1;i<=N_GEAR && diff[i];i++, left_direction *= -1)
			rotate(gear[i].begin(), (left_direction==1? gear[i].end() - 1 : gear[i].begin() + 1), gear[i].end());

		for(int i=gear_idx-1;i>0 && diff[i];i--, right_direction *= -1)
			rotate(gear[i].begin(), (right_direction==1? gear[i].end() - 1 : gear[i].begin() + 1), gear[i].end());
	}
	vector<int> squared = {0, 1, 2, 4, 8};
	for(int i=1;i<=N_GEAR;i++){
		if(gear[i][0])
			answer += squared[i];
	}
	cout << answer << "\n";


	return 0;
}

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

using namespace std;

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

	int N;
	cin >> N;

	cout << (N%2? "CY\n" : "SK\n");
	
	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<int> children(N, 0), dp(N, 1);
	
	for(int i=0;i<N;i++)
		cin >> children[i];
	
	for(int i=0;i<N;i++)
		for(int j=i-1;j>=0;j--)
			if(children[i] > children[j])
				dp[i] = max(dp[i], dp[j] + 1);

	cout << N - *max_element(dp.begin(), dp.end()) << "\n";

	return 0;
}

/*
	LCS 2
	DP
	Top-down
    길이만 구할 수 있었다..
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1000

using namespace std;

string A = "", B = ""; 
vector<vector<int>> dp(MAX, vector<int>(MAX, -1));

int solve(int A_idx, int B_idx){
	if(A_idx == A.length() || B_idx == B.length())
		return 0;
	if(dp[A_idx][B_idx]>=0)
		return dp[A_idx][B_idx];
	for(int i=A_idx;i<A.length();i++){
		for(int j=B_idx;j<B.length();j++){
			if(A[i] == B[j]){
				dp[A_idx][B_idx] = max(dp[A_idx][B_idx], solve(i+1, j+1)+1);
			}
		}
	}
	return dp[A_idx][B_idx];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> A >> B;
	
	cout << solve(0, 0) << "\n";

	return 0;
}

/*
	LCS 2
	DP
	Bottom-up
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1000

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	string A = "", B = ""; 
	cin >> A >> B;
	
	vector<vector<int>> dp(MAX, vector<int>(MAX, 0));

	//길이 구하기
	for(int i=1;i<=A.length();i++){
		for(int j=1;j<=B.length();j++){
			if(A[i-1] == B[j-1]){
				dp[i][j] = dp[i-1][j-1] + 1;
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
	cout << dp[A.length()][B.length()] << endl;
	
	//경로 찾아가기
	string answer = "";
	
	int x = A.length();
	int y = B.length();
	
	while(dp[x][y]>0){
		if(dp[x][y] == dp[x-1][y]){
			x--;
		} else if(dp[x][y] == dp[x][y-1]){
			y--;
		} else {
			answer = A[x-1] + answer;
			x--;
			y--;
		}
	}
	cout << answer << endl;
	return 0;
}

/*
	주식
	단순 구현
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	cin >> T;

	while(T--){
		long long N, answer = 0;
		cin >> N;
		vector<long long> stock(N);
		vector<long long> sellPrice(N, 0);

		for(int i=0;i<N;i++)
			cin >> stock[i];
		
		for(int i=N-2;i>=0;i--)
			sellPrice[i] = max(sellPrice[i+1], stock[i+1]);

		for(int i=0;i<N;i++)
			answer += max((sellPrice[i] - stock[i]), (long long)0);
		cout << answer << endl;
	}

	return 0;
}