백준 랜덤마라톤 #18

Jinhuyk Mun

Student. CSE

Daily Study Algorithm PS

백준 랜덤마라톤 #18

Oct 15, 2024

ps
random

백준 랜덤마라톤 #18 문제풀이

BOJ 25756 [B3] - 방어율 무시 계산하기

단순계산 문제

#include <bits/stdc++.h>
using namespace std;

int main(void){
    cin.tie(0)->sync_with_stdio(0);
    int N;
    double V = 0.0;

    cin >> N;
    cout.fixed;
    cout.precision(10);
    while(N--){
        double A; cin >> A;
        V= (1-((1-(0.01*V))*(1-(0.01*A))))*100;
        cout << V <<"\n";
    }
}

BOJ 30111 [S4] - 겹다각형의 각

여러번 도형을 그려가면서 일반화를 시키다보면 다음을 얻을 수 있음.
처음 각의 합은 (처음 각의 개수-2)*180
두번째부터는 처음각의 합에 (각의 개수)*180

#include <bits/stdc++.h>
using namespace std;

int main(void){
    cin.tie(0)->sync_with_stdio(0);
    int N;
    cin >> N;
    vector<int> k(N);
    for(auto &i : k) cin >> i;
    reverse(k.begin(),k.end());
    int A = (k[0]-2)*180;

    for(int i = 1; i<k.size();i++){
        A+= 180*k[i];
    }
    cout << A <<"\n";
}

BOJ 31672 [S3] - 특별한 케이크 (easy)

실버문제이기는 하나, 난이도는 골드급이었음
i번째의 정보를 저장후에 , i번 차례인 경우 해당 정보만 뒤집은 후, i번의 정보가 담긴 모든 수가 1 (범인) 인 경우에만 범인 리스트에 넣었음

#include <bits/stdc++.h>
#include <cstdio>

using namespace std;

int main(void){
    string str;
    getline(cin, str);
    int N; cin >> N;
    vector< vector<int> > d(N+1, vector<int>(2,0));
    vector<pair<vector<int>, int>> Q(N+1);
    for(int i = 1; i<=N;i++){
        int M; cin >> M;
        vector<int> S(N+1,0);
        while(M--){
            int s; cin >> s;
            S[s] = 1;
        }
        int j; cin >> j;
        Q[i] = {S,j};
        for(int i = 1 ;i<=N;i++){
            d[i][(j==1?S[i] : !S[i])]++;
        }
    }
    vector <int> ans ;

    for(int i = 1; i<=N;i++){
        int k = Q[i].first[i];
        if(Q[i].second == 1) (k = k == 0 ? 1 : 0);
        int z = d[i][0];
        int o = d[i][1];
        if(k == 0){
            z++;
            o--;
        }
        else{
            z--;
            o++;
        }
        if(z == 0) ans.push_back(i);
        
    }
    if(ans.empty()) cout << "swi";
    else{
        sort(ans.begin(), ans.end());
        for(auto i : ans ) cout << i <<" ";
    }

}

BOJ 18291 [G5] - 비요뜨의 징검다리 건너기

큰수의 거듭제곱 문제와 동일

#include <bits/stdc++.h>

using namespace std;
int fast_pow(int x, int n, int m){
	if(n == 0) return 1 % m;
	long long u = fast_pow(x,n>>1, m);
	u = (u*u)%m;
	if(n&1) u = (u*x)%m;
	return u;
}
int main(void){
	cin.tie(0)->sync_with_stdio(0);
	int T, N;
	cin >> T;
	while(T--){
		cin >> N;
		if(N == 1) cout << 1 <<"\n";
		else cout << fast_pow(2,N-2,(int)1e9+7) <<"\n";
	}
}

BOJ 17498 [G5] - 폴짝 게임

NM 의 최대만 나와있으므로, iM +j 로 카운팅 해주는 방법을 생각할 수 있음
DP 문제

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll INF = 1e12;
int N, M , D;
ll a[200200];
ll d[200200];


ll dp(int cur){

	if(cur  >= N*M ) return -INF;
	int x = cur / M;
	int y = cur % M;

	if(x == N-1) return 0;
	ll &ret = d[cur];

	if(ret != -INF) return ret;
	for(int i = x+1; i<=x+D;i++){
		for(int j = y-D; j<= y+D;j++){
			if((0<=i && i<N && 0<=j && j<M) && (abs(i-x)+abs(j-y) <= D)){
				ret = max(ret, a[cur]*a[i*M+j] + dp(i*M+j));
			}
		}
	}
	return ret;
}

int main(void){
	cin >> N >> M >> D;

	for(int i = 0;i <N;i++){
		for(int j = 0; j<M;j++){
			cin >> a[i*M+j];
			d[i*M+j] = -INF;
		}
	}
	ll ans = -INF;
	for(int i = 0;i<M;i++) ans = max(ans, dp(i));
	cout << ans <<"\n";

}

BOJ 19597 [G5] - 문자열 뒤집기

S[i][0] 에는 뒤집히지 않은 문자열, S[i][1]에는 뒤집힌 문자열 저장
최대한 사전순으로 앞에 와야하므로, dfs 를 이용하여 접근가능

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


string rv(const string& s){
	string ret = s;
	reverse(ret.begin(),ret.end());
	return ret;
}

int main(void){
	cin.tie(0)->sync_with_stdio(0);
	int T, N;
	cin >> T;
	while(T--){
		cin >> N;
		vector<vector<string>> S(N,vector<string>(2));
		vector<int> d(N);
		for(int i = 0;i<N;i++) {
			cin >> S[i][0];
			S[i][1] = rv(S[i][0]);
		}
		bool f = true;
		auto DP = [&](int cur, auto&& DP){
			if(cur == N){
				for(auto i : d) cout << i;
				f = false;
				return;
			}
			for(int i = 0; f && i<2;i++){
				if(cur == 0|| S[cur -1][d[cur-1]] <= S[cur][i] ){
					d[cur] = i;
					DP(cur+1,DP);
				}
			}
		};
		DP(0,DP);
		cout <<"\n";
	}

}

BOJ 9177

DP 문제
두 단어의 인덱스를 인자로 하여, 생성문자열 R과 같은 지 비교하면서 풀어야함

#include <bits/stdc++.h>
using namespace std;

int main(void){
	cin.tie(0)->sync_with_stdio(0);
	int T; cin >> T;
	string A,B,R;
	int d[303][303];
	auto dfs = [&](int a, int b, auto&& dfs)-> bool {
		if(a == A.size() && b == B.size()) return true;

		auto &ret = d[a][b];
		if(ret != -1) return ret;
		if(a < A.size() && A[a] == R[a+b] && dfs(a+1,b,dfs)) ret =true ;
		else if(b<B.size() && B[b] == R[a+b] &&  dfs(a,b+1,dfs)) ret =true;
		else ret = false;
		return ret;
	};

	for(int tc = 1; tc<=T;tc++){

		cin >> A >>B >>R;
		memset(d,-1,sizeof(d));
		cout <<"Data set "<< tc <<": "<< (dfs(0,0,dfs) ? "yes" : "no")<<"\n";

	}
}

BOJ 16947 [G3] - 서울 지하철 2호선

Cycle을 찾은 후에 BFS로 cycle과의 거리를 측정하면 됨

#include <bits/stdc++.h>
using namespace std;

int main(void){
	cin.tie(0)->sync_with_stdio(0);

	int N;
	cin >> N;
	vector<int> g[3003];
	for(int i = 0;i<N;i++){
		int u,v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	vector<bool> visited(N+1,false);
	vector<bool> isCycle(N+1,false);
	int prev[3003];
	bool flag = false;
	auto _cycle = [&](int cur,auto&& _cycle){
		visited[cur] = true;

		for(auto i : g[cur]){
			if(flag) return;
			if(visited[i]){
				if(i != prev[cur]){
					isCycle[cur] = true;
					flag = true;
					while(cur != i){
						isCycle[prev[cur]] = true;
						cur = prev[cur];
					}
					return;
				}
			}
			else{
				prev[i] = cur;
				_cycle(i,_cycle);
			}
		}
	};
	_cycle(1,_cycle);

	for(int i = 1; i<=N;i++){
		if(isCycle[i]) cout << "0 " ;
		else{

			vector<int> dst(N+1,0);
			vector<bool> vst(N+1,false);
			queue <int> Q;
			int p = 0;
			Q.push(i);

			while(!isCycle[Q.front()]){
				int c = Q.front();
				Q.pop();
				vst[c] = true;
				for(auto u : g[c]){
					if(vst[u]) continue;
					dst[u] = dst[c] +1;
					Q.push(u);
				}
			}
			cout << dst[Q.front()] <<" ";
		}

	}

}