마라톤이 갱신 돼서 다시 풀어봤다.
이번에는 마지막 문제가 골드라 어떤 문제일까 기대하며 문제를 풀었다.
문제 + 풀이
[문제 후기]
A. 직사각형 (1분)
문제 링크
이 문제는 진짜 단순히 A*B를 출력하는 문제라 어려울 게 없는 문제였다...
구현
#include <iostream>
using namespace std;
int main() {
int A, B;
cin >> A >> B;
cout << A * B;
}
B. Check the Check (14분)
문제 링크
어려운 문제는 아닌데, C++에서 문자열 입력을 받는게 익숙하지 않아서 오래 걸린 문제다.
단순히 곱셈으로 실제 지불해야하는 가격과 지불하기를 바라는 가격을 비교한다. 이후 실제 지불해야 하는 가격이 더 낮아 적은 가격을 내도 되면 PAY를 출력하고, 더 많은 돈이 가격표에 적혀져 있으면 PROTEST를 출력하면 되는 문제다.
한 줄에 음식의 이름이 들어오기 때문에 getline(cin,str) 으로 음식의 이름을 입력 받았다.
여기서 주의해야할 점은 cin으로 음식의 가격, 개수를 입력 받은 뒤에는 cin.ignore()를 이용해 버퍼에서 \n을 비워 주어야 다음에 다시 getline으로 제대로 된 음식의 이름을 입력 받을 수 있다.
구현
#include <iostream>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int cost=0,pay, n, m;
string str;
while (true) {
getline(cin,str);
if (str == "TOTAL") {
cin >> pay;
break;
}
else{
cin >> n >> m;
cost += n * m;
}
cin.ignore(); // 버퍼 비우기
}
if (cost >= pay) {
cout << "PAY";
}
else {
cout << "PROTEST";
}
return 0;
}
C. 이진 딸기 (17분)
문제 링크
이진법으로 수를 바꾸는 문제다.
단지 1을 딸기, 0을 V로 표시만 하면 된다.
여기서 규칙이 있는데, 1에서 시작해 15까지 부르면 다시 14, 13 ... 2, 1 을 반복한다.
그러므로 수를 말하는 차례가 28번 지나면 다시 처음의 1로 돌아온다. 이를 이용해 N번째 차례일 경우 N%28번째 차례와 같은 수를 외친다.
이를 이용해 1~28번째 차례에 어떤 수를 외치는지 배열에 저장하고, N%28 연산을 해 몇 번째 차례의 수와 똑같은지 계산해 출력했다.
구현
#include <iostream>
#include <string>
using namespace std;
void bi(int d, int nowN)
{
if (nowN % 2==1)
{
nowN /= 2;
if (nowN > 0)
{
bi(d + 1, nowN);
}
else {
if (4 - d > 0) {
for (int i = 0; i < 4 - d; i++) {
cout << "V";
}
}
}
cout << "딸기";
}
else {
nowN /=2 ;
if (nowN>0)
{
bi(d + 1, nowN);
}
else {
if (4 - d > 0) {
for (int i = 0; i < 4 - d; i++) {
cout << "V";
}
}
}
cout << "V";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int T, N;
// int a =1 ~ 15 ~ 2 == 28개
int a[29];
for (int i = 1; i < 16; i++) {
a[i] = i;
}
for (int i = 1; i < 14; i++) {
a[i + 15] = 15 - i;
}
cin >> T;
for (int i = 0; i < T; i++) {
cin >> N;
N %= 28;
if (N == 0) {
N = 28;
}
bi(1, a[N]);
cout <<"\n";
}
return 0;
}
D. Cow Race(49분)
문제 링크
푸는데 매 오래 걸린 문제다. 문제가 영어였고, 어떻게 시간을 비교할까 쓸데 없는 고민을 너무 많이 했기 때문이다.
먼저 주의해야할 점은 처음에 같은 지점에서 출발해 리더가 바뀌는 경우에는 리더쉽 변경으로 세지 않는다.
그리고 리더쉽이 변경될 경우는 한 소가 다른 소를 추월했다는 의미다. 잘 생각해보면 소들의 속도가 변경되지 않는 한 한번 리더쉽이 변경되면 속도가 일정하기 때문에 리더쉽이 변경되지 않는다.
이를 이용해 소들의 속도가 변경되는 지점을 기준으로 삼고, 그 지점마다 소들의 위치를 계산했다.
만약에 이전에 A 소가 B 소 보다 앞에 있거나 같은 위치였는데, 이후에 속도가 바뀐 지점에서 B소가 A소 앞에 있다면 리더쉽 변경이 일어난 것이다.
이렇게 속도가 변경되는 지점을 찾고 오름차순으로 정렬해 그 지점마다 소들의 위치를 비교하면 리더쉽이 몇 번 변경 됐는지 계산할 수 있다.
+ 처음부터 끝까지 속도가 같은 경우는 리더쉽 변경이 0이라는 점에 유의해야하며, 처음부터 끝까지 A소가 B소보다 빠른 경우에도 리더쉽 변경은 없었다는 점에 유의해야한다.
구현
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<pair<int,int>> A(N), B(M);
int sp, ti, nt=0;
vector<int> time;
for (int i = 0; i < N; i++) {
cin >> sp >> ti;
nt += ti;
A[i] = { sp,nt }; //nt까지는 sp로 달린다.
time.push_back(nt);
}
nt = 0;
for (int i = 0; i < M; i++) {
cin >> sp >> ti;
nt += ti;
B[i] = { sp,nt }; //nt까지는 sp로 달린다.
time.push_back(nt);
}
sort(time.begin(), time.end());
int aSp, bSp, aidx = 0, bidx = 0, am=0,bm=0;
aSp = A[aidx].first, bSp = B[bidx].first;
nt = 0;
int aFast = 2; //원래 같음, 1은 a빠름 0은 b가 빠름
int ans = 0;
for (int i = 0; i < time.size(); i++)
{
am += (time[i] - nt) * aSp;
if (aidx < N-1) {
if (A[aidx].second <= time[i]) { // A의 시간이 time의 시간과 같다면, A가 속도가 바뀔 타이밍
aidx++;
aSp = A[aidx].first;
}
}
bm += (time[i] - nt) * bSp;
if (bidx < M-1) {
if (B[bidx].second <= time[i]) { // A의 시간이 time의 시간과 같다면, A가 속도가 바뀔 타이밍
bidx++;
bSp = B[bidx].first;
}
}
nt = time[i];
if (am == bm)
{
aFast = 2;
}
else if (am > bm)
{
if (aFast!=1)
{
ans += 1;
}
aFast = 1;
}
else if (bm > am) {
if (aFast != 0) {
ans += 1;
}
aFast = 0;
}
}
if (ans == 0) {
cout << 0;
}
else {
cout << ans -1 << endl;
}
return 0;
}
E. Small PhD Restaurant (6분)
문제 링크
A번 문제를 제외하면 이번 마라톤 중에 가장 빠르게 해결한 문제다. 저번에도 E번 문제를 가장 빨리 풀었는데;;
이 문제는 단순한 문제다. A_i원을 지불해 B_i원의 가치를 얻을 수 있다. 이 경우 가장 많은 재화를 갖게 될 경우 얼마의 재화를 갖고 있는지 출력하면 된다.
단순히 A_i를 기준으로 오름차순 정렬한 다음 A_i<B_i가 성립되면 물건을 산다.
그리고 현재 돈이 A_i보다 작다면, A_i 뒤의 어떤 물건도 살 수 없으므로 현재 재화를 출력하고 코드를 종료하면 된다.
(오름차순으로 정렬되었기 때문에 A_i를 살 수 없다면 재화를 더 늘릴 수 없으므로 A_(i+k)번째 물건을 살 수 없기 때문)
구현
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<pair<int, int>>V(N);
for (int i = 0; i < N; i++) {
cin >> V[i].first;
}
for (int i = 0; i < N; i++) {
cin >> V[i].second;
}
sort(V.begin(), V.end(), [](pair<int, int> a, pair<int, int> b) {
return a.first < b.first;
});
for (int i = 0; i < N; i++) {
if (V[i].first<V[i].second){
if (V[i].first <= M) {
M += V[i].second - V[i].first;
}
else {
break;
}
}
}
cout << M;
return 0;
}
F. Fair Play (11분)
문제 링크
문제를 풀 때는 생각보다 빨리 풀었지만, 다시 생각해보면 은근히 헷갈릴 수 있는 문제다.
당구에서 (A기술 점수, B기술 점수)를 개인마다 갖고 있으며, 2명씩 짝을 지어 팀을 만든다.
이 때, 각 팀의 개인 기술 점수를 합쳐 팀의 (A기술 점수 B기술 점수)를 만든다. 그리고 모든 팀의 A기술점수가 같고 B기술점수를 같게 만들 수 있다면 possible, 만들 수 없다면 impossible을 출력하면 되는 문제다.
이 문제에서 모든 경우를 고려할 필요는 없다. 왜냐하면 2명씩 팀을 이루기 때문에 기술점수를 정렬해 가장 점수가 낮은 사람은 가장 기술점수가 높은 사람과 팀을 짜는 식으로 문제를 풀면 되기 때문이다.
예를 들어 N명의 사람을 A기술을 기준으로 오름차순 정렬을 했다고 가정하자.
그러면 A_1은 A_N과 팀을 이루어야한다.
왜냐하면 A_1<A_2일 경우 A_2가 A_N과 팀을 이루면 A_1과 팀을 이루는 사람을 M번째 사람이라고 했을 때
$$ A_M \leq A_N, \;\; (M<N)\;\; 이므로\;\; A_1+A_M<A_2+A_N$$
이 항상 성립하기 때문에 모든 팀의 점수를 같게 할 수 없기 때문이다.
그러므로 정렬 후 기술점수가 높은 사람은 기술점수가 낮은 사람과 짝을 지어 나가면 된다.
마찬가지로 정렬할 때 A기술 점수가 같을 경우 B기술점수도 오름차순으로 정렬하도록 하면 된다.
B 기술 점수도 정렬로 풀 수 있는 이유는 위와 같이 가정을 통해 귀류법으로 검증하면 된다.
+ 참가자가 홀수인 경우 예외처리를 해주어야 한다.
구현
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
int a, b;
vector<pair<int, int>> V(N);
for (int i = 0; i < N; i++) {
cin >> a >> b;
V[i] = { a,b };
}
sort(V.begin(), V.end(), [](pair<int, int>a, pair<int, int>b) {
return a.first == b.first ? a.second < b.second : a.first < b.first; });
if ( N%2 == 1) {
cout << "impossible";
return 0;
}
int fi = V[0].first + V[N - 1].first, se = V[0].second + V[N - 1].second;
for (int i = 1; i < N/2; i++) {
if (fi != V[i].first + V[N - i - 1].first || se != V[i].second + V[N - i - 1].second) {
cout << "impossible";
return 0;
}
}
cout << "possible";
return 0;
}
F. 謎紛芥索紀 (Large) (18분)
문제 링크
이 문제는 미분을 한 뒤 2를 x에 대입해 값을 계산하면 되는 문제다.
여기서 중요한 점은 차수가 최대 10^9가 되기 때문에 2^(10^9 - 1)을 계산해야되는 경우가 생긴다는 점이다.
2^n을 빠르게 계산하기 위해서 분할정복을 사용하면 된다.
$$ 2^n = 2^(n/2)*2^(n/2)$$
을 이용해 재귀로 계산하면 아무리 많아도 한 차수당 log(10^9)번 계산하면 되기 때문에 빠르게 문제를 해결할 수 있다.
이후 모든 항에 대해 계산을 해 100000007로 나누어 주면 쉽게 풀 수 있는 문제다.
구현
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
long long calc(long long kk) // 2^k를 계산
{
if (kk == 0) {
return 1;
}
if (kk == 1) {
return 2;
}
long long tmp;
tmp = calc(kk / 2) % mod;
if (kk % 2 == 1) {
return (tmp * tmp * 2) % mod;
}
else {
return (tmp * tmp) % mod;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
long long ans = 0;
long long c, k;
for (int i = 0; i < N; i++) {
cin >> c >> k;
int test = calc(k - 1);
ans += ((((c * k)%mod) * calc(k-1))%mod)%mod;
}
cout << ans % mod << endl;
return 0;
}
G. 소수인팰린드롬 (48분)
문제 링크
생각보다 오래 걸린 문제다.
중간에 0이 들어가는 경우를 고려하지 않았기 때문이다.
팰린드롬이 되려면 앞뒤에 같은 수가 들어오면 되기 때문에 string을 이용해 앞 뒤에 한 글자씩 추가했다.
예를 들어 앞에 1이 추가되면 뒤에 1이 추가되어야 팰린드롬이 되기 때문이다.
이후 string으로 만든 수를 int로 바꿔주고 소수인지 판단하는 검사를 했다.
여기서 소수인지 판단하는 방법은 얻은 수 N을 2~root(N)사이의 수로 나누어 보는 것이다.
만약 그 사이의 수로 나누어지면 소수가 아니다.
여기서 root(N)까지만 검사하면 되는 이유는 root(N)~N-1사이의 수 M으로 나누어 떨어지면 M과 곱해 N을 만들 수 있는 수 K가 2~root(N) 사이에 존재해야 한다. 그렇기 때문에 개수가 더 적은 2~root(N) 사이의 수 로 N을 나누어 검사를 하면 root(N)의 시간복잡도로 빠르게 계산할 수 있다.
+ string을 int로 바꾸는 stoi함수에서 string의 값이 int값을 벗어나면 에러가 뜨기 때문에 주의해야 한다.
추가로 다른 사람의 풀이를 봤는데 1~9999까지의 수를 이용해 팰린드롬을 만드는 방법이 있었다;;
ex) 임의의 수가 237 이면, 237732의 팰린드롬을 만들어 검사한다.
구현
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
set<long long> palin;
//소수 검사
void isPalin(long long nowN)
{
if (nowN == 0) {
return;
}
if (nowN == 1) {
return;
}
if (nowN == 2) {
palin.insert(2);
return;
}
for (int i = 2; i < pow(nowN, 0.5) + 1; i++) {
if (nowN % i == 0) {
return;
}
}
palin.insert(nowN);
return;
}
//팰린드롭 검사
void calc(int a, int b, string nextN)
{
// 앞뒤에 수 추가
if (nextN.length() >= 9) {
return;
}
long long nowN = stol(nextN);
if (nowN > b) {
return;
}
if (nowN >= a) {
isPalin(nowN);
}
for (int i = 0; i < 10; i++) {
char c = '0' + i;
string str = c + nextN + c;
calc(a, b, str);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int a, b;
cin >> a >> b;
string ss = "";
for (int i = 0; i < 10; i++) {
char tc = '0' + i;
calc(a, b, tc + ss + tc);
calc(a, b, ss + tc);
}
vector<long long> tv(palin.begin(), palin.end());
sort(tv.begin(), tv.end());
for (int i = 0; i < tv.size(); i++) {
cout << tv[i] << "\n";
}
cout << -1;
return 0;
}
[풀이 후기]
이번에는 2시간 44분이 걸렸다.
c++에서 string을 자주 이용하지 않기 때문에 string을 사용한 풀이에서 시간이 오래 걸렸기 때문이다...
다시 생각해보면 이렇게 오래 걸릴 문제는 아니였는데 ㅠㅠㅠ
다음에는 더 빠르게 풀도록 집중해보자
'Algorithm > BAEKJOON' 카테고리의 다른 글
| [백준/C++] 선분 교차 3 (No. 20149) (0) | 2024.06.17 |
|---|---|
| [백준/C++] 선분 교차 2 (No. 17387) (0) | 2024.06.16 |
| [백준/C++] 기말고사 작품전시 (No. 28094) (0) | 2024.06.15 |
| [백준/C++] 보석 도둑 (No. 1202) (0) | 2024.06.12 |
| [백준/C++] 다각형의 면적 (No. 2166) (0) | 2024.06.11 |