02. CodeForces Round #704 (Div.2) 풀이 & 후기

대회 소감

두 번째 CodeForces 대회였다. 뒤에서도 언급하겠지만, 여러모로 너무나도 허무했던 시험이었다. 다음 Contest를 빨리 봐서 극복하고 싶다는 의지를 강력하게 점화해준, 어찌보면 고마운..? 시험이라고 생각하자 ^____^

풀이

A (Three Swimmers)

문제 보기

A번 문제 풀이 + 본인의 코드

굉장히 쉽게 풀었는데, C언어의 나눗셈을 실수하여 삽질한 문제. 정수 형태의 나눗셈을 해주려면 (long double) a/b 이런 식으로 앞에 형 변환을 해주어야 하는데, 이걸 새까맣게 잊고 있었다.본인이 발견하고도 굉장히 어이가 없었다…
오히려 ‘A번이 늦어지고 있다’는 것에 너무 신경이 쓰여서 집중해서 발견하지 못한 것 같다. 디버깅을 통해 충분히 찾아낼 수 있었는데,, 초반인 만큼 더더욱 중요하지 않은 곳에서 삽질할 확률이 높으니, 침착함을 유지하는 것이 중요하다고 느꼈다. 특히나 A, B번에서는 말이다.

교훈

• WA가 떠도 침착하게 디버깅하자.
  • 문제 다시 읽어보기 ➡ 올바르게 풀었는지 확인 ➡ 디버깅 (실수 잡기)

'Round #704 - A.cpp : AC'

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#ifdef __APPLE__
#include "dbg.h"
#else
#define dbg(...)
#endif
 
long long int p, a, b, c;
 
long long int func(long long int x) {
    auto temp = (long long int)(ceil((long double)p/x));
    dbg(temp);
    return (temp*x - p);
}
 
int main()
{
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%lld %lld %lld %lld", &p, &a, &b, &c);
        printf("%lld\n", min({func(a), func(b), func(c)}));
    }
}

B (Card Deck)

문제 보기

B번 문제 풀이 + 본인의 코드

A번에서 삽질을 하여 급하게 넘어와서인지, B번에서 더 많은 삽질을 해버렸다. 우선 맞았다고 생각한 알고리즘에서 TLE가 떠서, 멘탈이 나갔다. 이후 ‘틀렸을 리가 없어..’ 하면서 부분적 수정으로 시간 복잡도를 감소하려 했는데 여기서 정말 많은 try와 시간을 소모했다. (덕분에 C번 문제는 읽지도 못했다)

대회 시간이 끝나갈 때, 반 쯤 포기한 상태의 편한 마음가짐에서 생각하니 바로 아이디어가 떠올랐고, 3분만에 구현하여 AC를 받았다. A번도 그렇고, B번도 그렇고 여러모로 너무나도 허무한 contest였다 ㅜㅜ

교훈

• TLE가 떴으면 알고리즘 생각 자체를 다시 해야 할 확률이 높다. 시간복잡도를 정확히 계산해 보고, 정말 간당간당하게 못 넘겼다면 부분적 수정을 하되 그럴 일은 거의 없다. 부분적인 시간 복잡도 감소를 try하여 점수를 잃지 말자.
• 애초에 구현하기 전에, 시간복잡도를 계산하자. 특히 Worst Case의 시간복잡도.
• 스스로 시간을 정해 놓고, 그 안에 못 풀면 차라리 다음 문제로 넘어가자. 개인적으로 이번 상황에서는, TLE가 떴는데 즉석으로 아이디어가 떠오르지 않았을 때 바로 넘어가는 것이 맞지 않았나 싶다.

'Round #704 - B.cpp : AC'

#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef __APPLE__
#include "dbg.h"
#else
#define dbg(...)
#endif
 
stack<int> a;
stack<int> temp;
vector<int> b;
bool check[100002];
int n;
 
void func() {
    dbg(b);
    while(true) {
        int top = a.top();
 
        a.pop();
        temp.push(top);
 
        if(check[top]) {
            while(!temp.empty()) {
                int xx = temp.top();
                temp.pop();
                b.push_back(xx);
            }
 
            if(a.empty()) {
                return;
            } else {
                return func();
            }
        }  else {
            continue;
        }
    }
}
 
int main()
{
    int t;
    scanf("%d", &t);
    while(t--) {
 
        scanf("%d", &n);
        b.clear();
        int max = 0;
        memset(check, false, sizeof(check));
 
        for(int i = 0; i < n; i++) {
            int input;
            scanf("%d", &input);
            a.push(input);
            if(input > max) {
                max = input;
                check[input] = true;
            }
        }
 
        func();
 
        for(int i = 0; i < n; i++) {
            printf("%d", b[i]);
            if(i != n-1) {
                printf(" ");
            } else {
                printf("\n");
            }
        }
    }
}

C (Maximum Width)

문제 보기

C번 문제 풀이 + 본인의 코드

아직 Upsolving 하지 않았습니다.

D (Genius’s Gambit)

문제 보기

D번 문제 풀이 + 본인의 코드

아직 Upsolving 하지 않았습니다.