백준 제 1회 와쿠컵 후기(12솔) + 27965, 27972 풀이 (C++)

의도나 문제나 난이도나 전체적으로 매우 만족스러운 대회였다

충분히 코딩테스트에 나올 수 있는 문제들로, 초~중급 알고리즘의 대부분을 다루고 있다.

어려운 문제만 풀려고 덤빌 게 아니라 실버~골드 문제 랜덤 디펜스를 좀 해봐야겠다는 생각이 들었다

 

후기 :

A번 - 사칙연산

B번 - 비트연산(xor) or 1차원 배열. 좋은 문제

C번 - DP는 안되니까 규칙을 찾아내서 접근해야 함. 복제로 항상 이득을 볼 수 있으므로, 이진수의 자릿수 구하기 문제가 된다. 계속 2로 나눠주면 되고, 0일때의 예외처리가 필요하다. 좋은 문제
C번 문제를 재밌게 풀었다면 https://www.acmicpc.net/problem/11058 이 문제도 풀어보길 바란다.

D번 - substring 2개를 만들어서 그 두개의 처음부터 끝까지 비교하면 된다.(브루트포스) 시간제한이 넉넉하다.

E번 - 글 제대로 안 읽어서 틀림. 밀도 = 질량/부피 라는 사실만 알고 있으면 어렵지 않다

F번 - set쓰면 그냥 풀린다

G번 - 아래에 해설 있음. 정수론. 실버 3에 두기엔 좀 까다롭지 않나 싶다. 좋은 문제

H번 - 가장 간단한 경우를 생각하면 되고, 그 생각이 맞다. 경우의 수를 구하는 조합론 문제에 가깝다. 좋은 문제

I번 - 백트래킹으로 풀었는데 브루트포스도 된다고 함

J번 - 누적합이랑 이분탐색을 둘 다 활용해야 함. 좋은 문제

K번 - getline으로 string 입력 받고 조건만 잘 나눠주면 된다.

L번 - 규칙을 찾아내기가 그리 어렵지 않다. 이진법(2의 거듭제곱) 문제가 된다. 정말 좋은 문제

M번 - 그냥1차원배열로 닫힌 구간을 만들어 놓고 bfs를 돌리면 된다

N번 - 이거 왜 안되냐?? 하면서 계속 틀렸음. 그리디

O번 - 사칙연산을 응용해서 오프셋?을 만든다. 출력 시마다 그 오프셋을 곱하고 더해서 출력하면 된다. 좋은 문제

 

 

---- 이하는 대회 중 못 푼 문제들 풀이 ----

G번 - N결수(27965) 풀이

2가지 사전지식이 필요하다.

1. 모듈러 연산의 성질(합동식)
기본적인 정수론의 성질이다. 나머지 연산 시 곱셈/덧셈/뺄셈에 대해, 분배법칙?이 성립한다. 뭔말이냐면,
12316854987 을 445678로 나눈 나머지를 구한다고 할 때,
((12316800000 % 445678) + (54987 % 445678)) % 445678 이렇게 계산해도 결과가 같고,
((((123168%445678)*(100000%445678)) % 445678) + (54987%445678)) % 445678 이렇게 계산해도 결과가 같다

2. 반복문 없이 정수의 길이 구하기(log_10)
어떤 큰 정수의 자릿수를 구하기 위해 10으로 계속 나눠줄 필요 없이 log10함수를 이용하면 편함

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;

int main(void) {
	fastio;
    ll N,K;cin>>N>>K;
    ll ans = 0;
    for (ll i = 1; i <= N; i++)
    {
        ll leng = floor(log10(i)+1);
        while (leng--)
        {
            ans*=10;
        }
        ans+=i;
        ans%=K;
    }
    cout<<ans;
    return 0;
}

 

그냥 i=1부터 i=N까지 반복문 돌리면서 N결수 단계 늘리고, i의 자릿수만큼 10을 곱하고 i 더하면서 오버플로우 안나게 K로 잘 나눠주기만 하면 됨

 

N번 - 악보는 거들 뿐(27972) 풀이

아!!

실수하기 쉬워서 까다롭다. 아이디어 자체는 어렵지 않다

실수를 하도 많이 해서 대회 중 못 풀었다

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define int long long
using namespace std;

signed main(void) {
	fastio;
    int M;cin>>M;
    vector<int> v(M);
    for (int i = 0; i < M; i++)
    {
        cin>>v[i];
    }
    int mode = 0;//내림,중립,오름
    int prev = v[0];//이전의 음 높이
    int leng = 1;
    int down = 1;//내려가는 구간 길이 최대값
    int up = 1;//올라가는 구간 길이 최대값
    for (int i = 1; i < M; i++)
    {
        if(v[i]>prev){
            if(mode==0){
                leng = 2;
            }
            else if (mode==1)
            {
                leng++;
            }
            else if (mode==-1)
            {
                down=max(down,leng);
                leng = 2;
            }
            mode = 1;
        }
        else if(v[i]<prev){
            if(mode==0){
                leng = 2;
            }
            else if (mode==1)
            {
                up=max(up,leng);
                leng = 2;
            }
            else if (mode==-1)
            {
                leng++;
            }
            mode = -1;
        }
        prev=v[i];
    }
    if(mode==1){
        up=max(up,leng);
    }
    else if(mode==-1){
        down=max(down,leng);
    }
    cout<<max(up,down);
    return 0;
}

올라가는 구간의 올라가는 길이의 최대값, 내려가는 구간의 내려가는 길이의 최대값을 구해서

그 중 큰 것을 출력하면 되는데....여러모로 실수하기 쉬운 것 같다

 

---

총평 : 와쿠컵 정말 문제도 좋고 의도도 좋고 다 좋은 대회이기 때문에

주변에 프로그래밍에 입문하려는 친구가 있다면 꼭 추천해주고 싶다.

 

그리고... 아무리 풀 수 있는 문제만 잔뜩 있어도 그것을 제한 시간 내에 정확하게 풀어내는 건 어렵다고 다시 한 번 느낀다. 실수하면 안되는 데 자꾸 실 수 하 네