#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, t;
cin >> n >> m;
vector<int> arr(n + 1, 0);
while (m--) {
cin >> t;
for (int i = t; i <= n; i += t) arr[i] = 1;
}
int ans = 0;
for (int i = 1; i <= n; ++i) if (arr[i]) ans += i;
cout << ans;
}
백준 17174번: 전체 계산 횟수
생략.
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int ans = 0;
while (n) {
ans += n;
n /= m;
}
cout << ans;
}
백준 17175번: 피보나치는 지겨웡~
호출하는 횟수를 fib[n]이라 하면
n은 2부터, fib[n] = 1 + fib[n - 1] + fib[n - 2]이 성립.
#include <iostream>
using namespace std;
int main() {
int fib[51];
fib[0] = fib[1] = 1;
for (int i = 2; i <= 50; ++i) {
fib[i] = (1 + fib[i - 1] + fib[i - 2]) % 1000000007;
}
int n;
cin >> n;
cout << fib[n];
}
백준 17176번: 암호해독기
암호문의 숫자의 갯수와, 해독된 문장의 글자별 수를 잘 세서 똑같은지 확인하는 문제이다.
항상 느끼지만 중간에 공백이 들어간 문장을 한 줄 모두 읽는 것은 할 때마다 까다롭다.
cin, cout을 쓰려다 잘 안되어서 scanf와 getchar을 이용해 풀었다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, t;
scanf("%d", &n);
vector<int> cnt(53, 0);
for (int i = 0; i < n; ++i) {
scanf("%d", &t);
cnt[t]++;
}
char c;
getchar();
for (int i = 0; i < n; ++i) {
c = getchar();
if (c == ' ') cnt[0]--;
if (c >= 'A' && c <= 'Z') cnt[c - 'A' + 1]--;
if (c >= 'a' && c <= 'z') cnt[c - 'a' + 27]--;
}
for (int i = 0; i < 53; ++i) if (cnt[i] != 0) {
printf("n");
return 0;
}
printf("y");
}
백준 17177번: 내접사각형 만들기
뭔가 겁나 어려운 문제. 다행히 문제에서 톨레미의 정리라는 힌트를 줬다.
정확히는 톨레미의 정리의 역이 성립해야 하는데, 이는 문제에 쓰여져있지 않다. 다행히 톨레미의 정리는 역도 성립한다.
새로운 변의 길이를 x라 하면, 두 대각선의 길이는 피타고라스 정리에 의해 구할 수 있으며, 방정식을 풀어 x를 찾으면 된다.
약간 부실한 코드 같은데, 테이스케이스가 그리 빡세지는 않은 것 같다.
#include <iostream>
#include <cmath>
#define EPS 1e-5
using namespace std;
int main() {
int a, b, c;
cin >> a >> b >> c;
int p, q, r;
p = a;
q = 2 * b * c;
r = a * (c * c - a * a + b * b);
int d = q * q - 4 * p * r;
if (d < 0) {
cout << -1;
return 0;
}
double x;
x = (-q + sqrt(d)) / (2 * p);
if (x < 0) {
cout << -1;
return 0;
}
cout << (int)(x + EPS);
}
백준 17178번: 줄서기
문제의 설명이 전반적으로 깔끔하지 못하다.
"대기 공간이 문제에서는 5명 이상도 일렬로 서있을 수 있다"가 무슨 말인지를 이해하기 정말 힘들었다. 대기 공간의 크기가 무한하다는 말로 일단 이해하고 풀어보았다.
stack을 이용하는 문제인데, 입장 순서가 맞으면 입장시키고 아니면 대기 공간으로 보내버리면 된다.
오히려 정렬 쪽이 조금 더 까다로울 수 있는데, 단순히 string으로 비교하면 A-111이 A-2보다 더 앞서기 때문에 atoi 등을 이용해서 변환해주어야 한다.
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
using namespace std;
typedef pair<string, int> si;
bool comp(si& a, si& b) {
if (a.first[0] != b.first[0]) return a.first[0] < b.first[0];
return atoi(a.first.substr(2, a.first.size() - 2).c_str()) < atoi(b.first.substr(2, b.first.size() - 2).c_str());
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<si> arr(5 * n);
for (int i = 0; i < 5 * n; ++i) {
cin >> arr[i].first;
arr[i].second = i;
}
sort(arr.begin(), arr.end(), comp);
vector<int> num(5 * n);
for (int i = 0; i < 5 * n; ++i) num[arr[i].second] = i;
stack<int> line, wait;
for (int i = 5 * n - 1; i >= 0; --i) line.push(num[i]);
for (int i = 0; i < 5 * n; ++i) {
if (!wait.empty() && wait.top() == i) {
wait.pop();
continue;
}
bool in = 0;
while (!line.empty()) {
if (line.top() != i) {
wait.push(line.top());
line.pop();
}
else {
line.pop();
in = 1;
break;
}
}
if (!in) {
cout << "BAD";
return 0;
}
}
cout << "GOOD";
}
백준 17179번: 케이크 자르기
Binary search를 이용하는 문제.
케이크를 n조각으로 자를 때, 조각의 크기가 가장 큰 걸 찾아야 한다.
각 조각의 크기가 t일 때 최대 몇 조각이 나오는지는 쉽게 찾을 수 있으므로 Binary search를 쓰기 딱 적합하다.
#include <iostream>
#include <vector>
using namespace std;
int m, l;
vector<int> arr;
bool can_cut(int cut, int size) {
int now = 0;
int cnt = 0;
for (int i = 0; i <= m; ++i) {
now += arr[i];
if (now >= size) {
cnt++;
now = 0;
}
}
return cnt >= cut + 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n >> m >> l;
arr.resize(m + 1);
for (int i = 0; i < m; ++i) cin >> arr[i];
arr[m] = l;
for (int i = m; i > 0; --i) arr[i] -= arr[i - 1];
int t;
while (n--) {
cin >> t;
int low = 1, high = l;
while (high - low > 1) {
int mid = (low + high) / 2;
if (can_cut(t, mid)) low = mid;
else high = mid;
}
cout << low << '\n';
}
}
