Daily BOJ 22/01/10-22/01/16 - Haru.run

Daily BOJ 22/01/10-22/01/16

2022/01/16 # PS # solved.ac # Daily BOJ

⚠ 스포일러 주의 ⚠
이 글은 BOJ(백준 온라인 저지) 문제 해답을 포함하고 있습니다.

계절 학기 종강!

통계 과목을 3주간 들었는데 정말 하기 싫었다.
하지만 ML/DL할 때 사용한다고 하니 이 악물고 해야했다.
다행으로 계산기, 책, 강의자료, 울프람알파, 엑셀 다 허용되는 오픈북 시험이라 조금은 마음 놓고 풀었다.
들어야 하는 수학 강의 다 들었다~~~~

2022/01/11 화요일

#7806 GCD! [G4]

실버 선생님의 도움을 받은 문제
n이 10이고, k가 240이라 하면
- $240=2^4\cdot3\cdot5$
1. 10!중에 2의 개수와 4를 비교해서 작은 수 만큼이 n!과 k의 gcd의 2의 개수.
2. 마저 똑같이 하면 됨

int f(int N, int x) {
    int ans = 0;
    while(N!=0){
        ans += N/x;
        N/=x;
    }

    return ans;
}

N!에서 소수 x의 개수가 있는가 찾는 코드

참고하기 좋은 문제: #1676 팩토리얼 0의 개수

#1890 점프 [S2]

문제에 대한 예시 그림

예시에 써진 것을 그대로 dp테이블로 만들면 된다.
출력해야 할 것은 dp[N-1][N-1]

2022/01/12 수요일

#23832 서로소 그래프 [G1]

phi(2) + ... + phi(N)

#16563 어려운 소인수분해 [G4]

에라토스테네스 체를 좀 응용하면 최소 소인수도 들고 있을 수 있고 최대 소인수도 들고 있을 수 있고 그렇다.
by. 실버 선생님

vector<int> prime;
int minPrime[5000009];
void sieve(int n){
    for(int i=2; i<=n; i++){
        if(!minPrime[i]) prime.push_back(i);
        for(auto j: prime){
            if(i*j>n) break;
            minPrime[i*j]=j;
            if(i%j==0) break;
         }
    }
}

참고 문서: Linear-sieve

이제 n이 소수가 아닐 때마다 그걸 나누는 소인수가 minPrime[n]에 들어있는 것
그래서 그걸로 n을 나누고 또 그 다음으로 가고 하면 된다.

#11688 최소공배수 찾기 [G4]

#7806 GCD!이랑 접근이 비슷함
lcm(A, B)의 소인수가 가지는 개수를 L과 비교해서 C를 만들어가면 된다.

2022/01/13 목요일

#2014 소수의 곱 [G1]

priority_queue(pq)를 이용하는 문제
1
priority_queue<int, vector<int>, greater<int>> pq;
작은 순서대로 받도록 하는 것.
다익?bfs? 돌듯이? while문을 돌면서 현재(now=pq.top())에 주어진 소수를 곱하면서(for 사용) 범위 안이면 push. 넘치면 break;
- 근데 이대로 하면 $3\cdot2$이 있는데 $2\cdot3$를 또 계산하려고 해서 now%x==0이면 나가게 걸어두면 된다
- x는 마지막으로 곱해준 수보다 작거나 같아야 해서 이렇게 걸어두면 됨

2022/01/14 금요일

#12107 약수 지우기 게임1 [G3]

실버스러운 문제에 대한 대화
본격 문제 만든 사람 앞에서 이 문제가 그사람스럽다고 말하기.

게임 이론 문제
나는 싫다 이런거…

각 상태마다 반드시 “이긴다” 아니면 “진다”라는 답이 있겠지? (모든 경우를 해보면 그중에 이기는 수가 있다 없다를 판단할 수 있으니까)
이기는 상태라면 “이걸 지우면 이긴다”라는 수가 존재할 것
1이 항상 지워진다는 것에 착안하여 전략을 세워야 함
by. 실버 선생님

#2421 저금통 [G5]

int ans = 1;
dp[1][1] = 1;
for(int k=1+2; k<=2+2*N; k++){
    for(int i=1; i<k; i++){
        int j = k-i;
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + cal(i, j);
        ans = max(ans, dp[i][j]);
    }
}
cout << dp[N][N]-1;

dp[i][j]: (i, j)일 때 소수의 개수
(1, 1) → (1, 2), (2, 1) → (1, 3), (2, 2), (3, 1) → ... 가는 것을 for로 구현했다. 표를 2배 더 그려야 하긴 하는데 알게 뭐람 $1\le N \le 999$인데

#18310 안테나 [S3]

1
2
3

sort(v.begin(), v.end());
if(N%2==1) cout << v[N/2];
else cout << v[N/2-1];

중간값 찾기

2022/01/15 토요일

#2212 센서 [G5]

정렬을 해서 센서와 센서 사이의 거리를 d[0]~d[N-1]까지 있을 것
거기서 K-1개를 빼면(N-K개 남기면) 그게 답
(3), (6, 7, 8, 10), (12, 14, 15), (18), (20)

#2015 수들의 합 4 [G5]

map<int, ll> m;
ll ans = 0;
for(int i=1; i<=N; i++){
    if(s[i]==K) ans++;
    ans += m[s[i]-K];
    m[s[i]]++;
}
cout << ans;

누적합을 구하는 배열 s[i]를 생성
원래는 d[j]-d[i-1]=K을 구하는건데 이제 그러면 d[i-1]=d[j]-K
나머지는 코드보면 됨

#1016 제곱 ㄴㄴ 수 [G1]

for(auto i: prime){
    if(i*i>MAX) break;
    ll st = MIN/(i*i);
    if(MIN%(i*i)!=0) st++;
    for(ll j=st; (i*i)*j<=MAX; j++){
        isSquare[(i*i)*j-MIN] = true;
    }
}

에라토스테네스의 체 느낌
st: MIN보다 살짝 큰 소수의 제곱으로 나누어 떨어지는 수
제한이 1 ≤ min ≤ 1,000,000,000,000이므로 그냥 배열에 넣으면 터지니깐 min ≤ max ≤ min + 1,000,000을 이용해서 isSquare에 수를 집어넣을 때 MIN만큼 빼자

#14567 선수과목 (Prerequisite) [G5]

위상 정렬을 정말로 정직하게 짜면 답이 나온다.
queue<pii> q해서 {now, cnt}저장

2022/01/16 일요일

#2870 수학숙제 [S4]

import re
N = int(input())
ans = []

for _ in range(N):
    tmp = ""
    s = input()
    tmp = re.findall("\d+", s)
    ans += list(map(int, tmp))

for x in sorted(ans):
    print(x)

C++로 도저히 짜기 싫어서 검색을 많이 했다…

import re를 이용하면 정규식을 쓸 수 있다
\d+를 쓰면 연속한 숫자를 찾을 수 있음 리스트([])로 반환
이것을 int로 변환해서 매핑해서 list로 바꿔서 ans에 추가로 저장함
sorted(ans): iterable한 데이터를 새로운 정렬된 리스트로 만들어서 반환

#24268 2022는 무엇이 특별할까? [S2]

int a[10] = {1, 0, 2, 3, 4, 5, 6, 7, 8, 9};
do{
    ll num = cal();
    if(num>N){
        cout << num;
        return 0;
    }
} while(next_permutation(a, a+D));

#10974 모든 순열에서 next_permutation을 썼으면서 기억을 못하고 결국엔 힌트 받아서 썼음.
배열 a가 좀 순서가 특별한 이유는 0으로 시작하는 숫자 막으려고, 그리고 저렇게 두고 돌리면 숫자가 내림차순으로 돌아가는데…

#24270 미니 버킷 리스트 [G4]

한별이가 귀엽다.

단위 시간을 더한 합을 S라 하면
정답은 $N! \cdot _{N+1}H_{K-S}$인데
약분약분하면 (K-S+1) + ... + (K-S+N)

후기

BOJ 800 solve!
2022/01/16 15:22

파이썬을 좀 더 잘 쓰고 싶다. 근데 이거는 ML/DL만지면 더 괜찮아질까 싶기도 한데 그거랑 이거랑 좀 다른 문법을 쓰는 것 같다고 느꼈는지라 브론즈 문제는 파이썬으로 푸는 연습을 해봐야 할 것 같다.
배운걸 까먹었던 나 자신이 바보같다. 이렇게 정리를 하면 조금은 낫지 않을까?
앞으로도 꾸준히 문제 풀고 정리하고 해서 알찬 1000문제 푸는 것을 하자. 항상 고생많고 너무 무리는 말자🥰
항상 도와주는 실버선생님과 사랑을 가득주는 정님에게 엄청난 감사를 남긴다🤗💕

# PS # solved.ac # Daily BOJ