백준 랜덤마라톤 #18 문제풀이
BOJ 27963 [B1] - 합금주화
- 수학
- 밀도 공식을 이용하여 d1,d2,x로 나타내면 되는 문제
#include <bits/stdc++.h>
using namespace std;
int main(void){
double d1,d2,x; cin >> d1 >> d2 >> x;
if(d1 > d2) swap (d1,d2);
x = (100 -x )/x;
cout.fixed;
cout.precision(10);
cout << (1+x)*d2 / ((d2*x/d1)+1);
}
BOJ 10845 [S4] - 큐
- queue를 구현하면 되는 문제
- deque를 이용하면 back 을 구현하기 편함
- 주의 할 점은 queue가 비어있는지가 중요함
#include <bits/stdc++.h>
using namespace std;
int main(void){
cin.tie(0)->sync_with_stdio(0);
int N; cin >> N;
deque <int> Q;
while(N--){
string s; cin >> s;
if(s == "push"){
int x; cin >> x; Q.push_back(x);
}
if(s == "pop"){
if(!Q.empty()) {cout << Q.front() <<"\n"; Q.pop_front();}
else cout << -1<<"\n";
}
if(s == "size") cout << Q.size()<<"\n";
if(s == "empty") cout << (Q.empty()? 1 : 0) <<"\n";
if(s == "front") cout << (!Q.empty()? Q.front() : -1 ) <<"\n";
if(s == "back") cout << (!Q.empty()? Q.back() : -1 ) <<"\n";
}
}
BOJ 31459 [S3] - 초콜릿과 ㄱ나이트 게임(Sweet)
- 크기가 X,Y인 보드를 쭉 순회하면서, c[i][j] = true 인경우에 c[i+x][j+y] 를 false로 바꿔주고, 최종적으로 true의 개수를 세주면 된다.
- 주의할 점은 i+x, j+y의 범위가 X,Y를 벗어날 수 있음이다.
#include <bits/stdc++.h>
using namespace std;
int main(void){
cin.tie(0)->sync_with_stdio(0);
int T; cin >>T;
bool ck[51][51];
while(T--){
int X,Y,x,y; cin >> X >>Y >> x >> y;
memset(ck,true,sizeof(ck));
int res = 0;
for(int i = 0; i<X;i++)
for(int j = 0; j<Y;j++)
if(ck[i][j]){
res++;
if(i+x <X && j+y <Y) ck[i+x][j+y] = false;
}
cout << res <<"\n";
}
}
BOJ 2777 [S2] - 숫자놀이
- 구현
- N을 계속해서 9부터 1 중 하나의 숫자로 나눠가면 됨
- N이 1일 경우가 예외이므로 이때만 처리해주면 됨
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
cin.tie(0)->sync_with_stdio(0);
int T; cin >>T;
while(T--){
int N; cin >> N;
int cnt = 0;
if(N == 1){
cout << "1\n";
continue;
}
for(int i =9; i>1;i--){
while(N%i == 0) {
cnt++;
N/=i;
}
if(N == 1) break;
}
cout << (N==1?cnt : -1)<<"\n";
}
}
BOJ 11497 [S1] - 통나무 건너뛰기
- greedy
- 통나무를 내림차순으로 정렬하고, i가 1부터 N-2까지는 L[i]-L[i-2]의 최대를, L[0]-L[1], L[0]-L[2], N이 짝수라면 L[N-2]-L[N-1], L[N-3]-L[N-1], 홀수라면 L[N-2]-L[N-1] 을 모두 비교하여 최대를 구하면 된다.
- abs를 안취하는 이유는 L은 이미 내림차순이므로, L[i] - L[j] 일때 i가 j보다 작으면 항상 0보다 크거나 같다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
cin.tie(0)->sync_with_stdio(0);
int T; cin >>T;
while(T--){
int N; cin >> N;
vector<int> L(N);
for(auto &i : L) cin >> i;
sort(L.begin(),L.end());
reverse(L.begin(),L.end());
int lev = 0;
lev = max(L[0]-L[1], L[0]-L[2]);
for(int i = 1;i<N-2;i++) lev = max(L[i]-L[i+2],lev);
if(N%2==0)lev = max(lev, max(L[N-2]-L[N-1], L[N-3]-L[N-1]));
else lev = max(lev, L[N-2]-L[N-1]);
cout << lev <<"\n";
}
}
BOJ 12348 [G5] - 분해합 2
- 수학
- 자연수 N의 생성자M은 N= M+M의 각 자리수인데, 이는 최대가 N의 크기만큼 9+9+..+9처럼 나타낸다. 그러므로 N은 N-9*N의 자리수 ~ N사이의 수가 된다.그리고 그 사이에서 생성자 M을 찾으면 된다. 이를 찾지 못하는 경우 생성자가 없으므로 0을 출력하면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
ll N; cin >> N;
int k =to_string(N).size()*9;
for(ll i = N-k;i<N;i++){
string s = to_string(i);
ll sum = i;
for(int j = 0;j<s.size();j++) sum += s[j]-'0';
if(sum == N){
cout << i <<"\n";
return 0;
}
}
cout << 0 <<"\n";
}
BOJ 23327 [G4] - 리그전 오브 레전드
- 전처리 하는 문제로서 추천하는 문제이다.
- 접근 방법은 $O(N^2Q)$ 에서 $O(NQ)$ 그리고 $O(Q)$이다.
$O(N^2Q)$
- 전체탐색을 해주면 된다.
- 당연히 TLE 이다.
$O(NQ)$
-
생각을 해보면
-
$\sum_{i=l}^r (a[i]{\sum_{k = i+1}^r}a[k])$
-
이 식을 만족해야하는데, 뒤 부분은 누적합을 이용해볼수 있다. 1부터 i 까지의 누적합을 $S[i]$라 한다면 식을 다음처럼 고쳐나갈 수 있다.
-
$\sum_{i=l}^r (ai)$
- 누적합은 전처리를 이용하여 $O(N)$에 전처리 과정을 수행하고 사용은 $O(1)$과 같다.
- 하지만 이 것도 TLE가 난다.
$O(Q)$
-
저 위에 식에서 더 줄일 수 없을까 하다가 다음처럼 식을 분해할 수 있음을 알수 있다.
-
$(S[r]\sum_{i=l}^r a[i] )- (\sum_{i=l}^r a[i]S[i])$
-
$a[i]S[i]$의 누적합을 $T[i]$라고 한다면 다음 식은 이렇게 바꿀 수 있다.
-
(Sr)- (T[r]-T[l-1])
-
이제 모두 누적합 배열로만 이루어진 식이 되었고, 모두 전처리를 통해 구현되어있으므로 $O(1)$만에 구할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
cin.tie(0)->sync_with_stdio(0);
int N, Q; cin >> N >>Q;
vector< ll > a (N+1), s(N+1), t(N+1);
for(int i = 1;i<=N;i++) {cin >> a[i]; s[i] = s[i-1]+a[i];}
for(int i = 1; i<=N;i++) t[i] = t[i-1] + a[i]*s[i];
while(Q--){
int l,r; cin >> l >> r;
ll res = s[r]*(s[r]-s[l-1]) - (t[r]-t[l-1]);
cout << res <<"\n";
}
}
BOJ 31220 [G3] - 연결된 지배집합
-
연결된 지배집합의 조건은 그래프 정점이 꼭 S에 속하거나, 인접해야하고, S는 모두 연결되어있어야한다는 점이다.
-
이때 N,M 칸에서의 연결된 지배집합을 찾기 위해서는 제일 적은 형태로 홀수칸은 000000…010 , 짝수칸은 111111…110 이 된다면 연결된 지배집합의 조건을 만족하고, NM/2 개로 구성이 가능하다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
int N, M;
cin >> N >> M;
cout << "YES\n";
string odd(M,'0');
odd[M-2] = '1';
string even(M,'1');
even[M-1] = '0';
for(int i = 1;i<=N;i++){
cout << (i%2== 1 ? odd : even) <<"\n";
}
return 0;
}