백준 랜덤마라톤 #17 문제풀이
BOJ 14219 [B2] - 막대과자 포장
- $N \times M %3 = 0 $ 인 경우 가능
BOJ 9417 [S4] - 최대 GCD
- math, string
- 모든 쌍에 대해 GCD를 취하면 되므로 $O(NN2^{31})$ 안에 해결이 가능
- 주어진 입력을 split 해야하는 문제 (연습해볼 필요가 있음)
#include <bits/stdc++.h>
using namespace std;
vector<string> split(string i, char delim){
vector<string> ret;
istringstream ss(i);
string tmp;
while(getline(ss,tmp, delim)){
ret.push_back(tmp);
}
return ret;
}
int main(void){
cin.tie(0)->sync_with_stdio(0);
int T; cin >>T;
cin.ignore();
while(T--){
string s;
getline(cin, s,'\n');
auto t = split(s,' ');
vector<int> v(t.size());
for(int i = 0;i <v.size();i++) v[i] = stoi(t[i]);
int ans = 0;
for(int i = 0;i<v.size()-1;i++){
for(int j = i+1; j<v.size();j++){
ans = max(ans, __gcd(v[i],v[j]));
}
}
cout << ans <<"\n";
}
}
다음처럼 stringstream을 이용하여 split 함수를 사용하였음
BOJ 2685 [S3] - 님비합
- math
- B진법으로 변환 후에 배열에 담고 계산해주면 됨 (기초 진법 변환)
#include <bits/stdc++.h>
using namespace std;
vector<int> conv(int x, int b){
vector<int> ret;
while(x) {ret.push_back(x%b); x/=b;}
return ret;
}
int main(void){
cin.tie(0)->sync_with_stdio(0);
int T; cin >>T;
while(T--){
int b,x,y; cin >> b >> x >> y;
if(x<y) swap(x,y);
auto X = conv(x,b), Y = conv(y,b);
for(int i = 0; i< Y.size();i++) X[i] = (X[i]+Y[i])%b;
int ret = 0;
for(int i = 0, j = 1; i<X.size();i++,j*=b){
ret += X[i]*j;
}
cout << ret<<"\n";
}
}
BOJ 14465 [S2] - 소가 길을 건너간 이유 5
- $O(NK)$는 TLE이기 때문에, 슬라이딩윈도우처럼 구간내 합을 이어나가면서 윈도우가 한칸씩 옆으로 지나갈때, 맨 앞과 맨뒤에 원소를 이용하여 합을 갱신해주면됨
#include <bits/stdc++.h>
using namespace std;
int main(void){
int N,K,B;
cin >> N >> K >> B;
vector <bool> tr(N+1,true);
while(B--){
int x ; cin >> x; tr[x] = false;
}
int cnt =0,ret = 0;
for(int i = 1; i<=K;i++){
if(tr[i]) cnt++;
}
ret = cnt;
for(int i = 2;i<= N-K+1;i++){
if(tr[i+K-1]) cnt++;
if(tr[i-1]) cnt--;
ret = max(ret,cnt);
}
cout << K-ret <<"\n";
}
BOJ 10917 [S2] - Your life
- BFS 기본 구현 문제
BOJ 6568 [G5] - 귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다
- 구현
- 컴퓨터 구조를 알면 조금은 간단하게 접근 가능한 문제
- bitset을 이용하면 조금 더 편하게 구현이 가능 (to_ulong())
- 정해진 8bit 안에서 오버 및 언더플로우가 발생하는 경우의 코드를 생각해볼 수 있음
#include <bits/stdc++.h>
using namespace std;
int main(void) {
string ins;
while(cin >> ins){
int mem[32];
for(int i = 0;i<32;i++){
if(i) cin >> ins;
bitset<8> byte(ins);
mem[i] = byte.to_ulong();
}
int pc = 0, adc = 0;
while(true){
int op = mem[pc]/32;
int addr = mem[pc]%32;
pc = ++pc &= 31;
if(op == 0) mem[addr] = adc;
else if(op == 1) adc = mem[addr];
else if(op == 2){ if(adc == 0) pc = addr;}
else if(op == 4) --adc &= 255;
else if(op == 5) ++adc &= 255;
else if(op == 6) pc = addr;
else if(op == 7) break;
}
bitset<8> ret = adc;
cout << ret <<"\n";
}
}
BOJ 31433 [S4] - KSA 문자열
- 원래 문자열 X 에서 KSA 문자열이 부분문자열로 존재할때의 개수를 센 다음에, 전체 길이에서 빼주면 됨
- 다만, 문자열 X 앞에 K나 KS가 붙는 경우도 생각해보아야함
- 위의 경우일 때에는, 개수 센것과 전체길이- k (k는 K 일때 1, KS 일떄 2) 를 비교하여 더 작은 개수를 사용해야함 (이것때문에 1시간을 소비했음) 그 이유는 K, KS는 임의로 붙여졌다고 생각하고 개수를 샌것이기 때문에 원래 개수센건 저 2가지 경우를 생각안함, 그래서 그 최소를 비교해야함.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
string s;
cin >> s;
string ksa = "KSA";
int ans = 1e9;
for(int k = 0;k<3;k++){
int idx = k,cnt = 0;
for(int i = 0;i<s.size();i++){
if(s[i] == ksa[idx %3]) {cnt++;idx++;}
}
cnt = min(cnt, (int)s.size()-k);
ans = min(ans, (int)s.size()-cnt);
}
cout <<2*ans;
}
BOJ 28076 [S3] - 멀티탭 충분하다
- 애드혹 문제
-
예시를 보면 멀티탭 3층을 쌓는 순간 처음 층과 단자 방향이 같다는 것을 알수 있음. 즉 3층마다 원래 쌓았던 멀티탭 위에 겹쳐서 쌓을 수 있음
- 그렇다면 3층을 한 묶음으로 봤을때, 1층이 L1, 2층이 L2, 3층이 L3 라고 한다면 L1은 L1보다 작고, L2 보다 큰 멀티탭이 겹쳐지면된다. L2는 L2보다 작고, L3 보다 큰 멀티탭이 겹쳐지면 된다.
그러므로 가장 먼저 멀티탭을 내림차순으로 정렬해놔야 한다.
이를 수식으로 피게 되면 L1,L2,L3의 가장 큰 멀티탭이 1번째 묶음(아래) 에 있을 것이고, 이 3개를 더해주고, 3을 빼주면 그것이 정답이 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
int N; cin >> N;
vector<int> a(N);
for(auto &i:a) cin >> i;
sort(a.begin(), a.end());
reverse(a.begin(), a.end());
if(N == 1) cout << a[0];
else if (N==2) cout << (a[0]+a[1]-1);
else{
int L1 = 1,L2,L3;
if(N%3 ==0) L2 = N/3 +1;
else L2 = N/3 +2;
if(N%3 ==2) L3 = L2 + N/3 + 1;
else L3 = L2 + N/3;
L1--, L2--,L3--;
cout << a[L1] + a[L2] + a[L3] -3;
}
}