Daily BOJ 22/01/17-22/01/23
2022/01/23 # PS # solved.ac # Daily BOJ

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



조증이 나를 의욕 뿜뿜으로 만드네

  • 적당히 사려야 하는데 그게 잘 안되네
  • 그냥 매일 하는 루틴을 최대한 지키기로 마음 먹었어. 여기서 더 무리하면 안되니깐…
    • 듀오링고 출첵
    • BOJ 5문제 → 풀이 정리
    • ML/DL 공부
    • 비올라 연습


2022/01/17 월요일

#6416 트리인가? [G5]

링크

여러가지 그래프의 모습

  • 트리의 성질 중 하나는
    • edge = node - 1
    • 사이클을 이루게 되면 저 위의 성질이 깨진다.
  • 위의 그림의 그래프와 같이 여러개가 하나를 가리키면 틀림
    1
    2
    3
    map<int, int> edge;
    // Do something
    if(edge.find(y)!=edge.end()) flag = false;
  • x, y를 받을 때 y에 연결된게 있는지 찾고, edge[y] = true로 만들어서 마킹함.
    • 연결된게 있는데 이러면 이것은 트리가 아님.
  • 나는 map<int, int> node;해두고 node[x]와 node[y]를 하나씩 증가해서 노드의 개수를 파악했다.
  • edge = node.size() - 1이면 트리. 아니면 !트리

#5550 헌책방 [G2]

링크

  • 책 종류에 대해 책의 가격들을 내림차순으로 정리할 필요가 있음
    1
    for(auto &g: v) sort(g.begin(), g.end(), greater<int>());
    • &붙여야 행을 돌아버림
  • 그리고 1권 팔았을때, 2권 팔았을 때,,, 의 매입가격을 구하는 누적합 배열을 하나 만들어서 이제 dp시작.
    • 여기서 같은 장르의 책을 T권 매입했을 때 매입 가격이 올라가는 것을 계산해서 집어넣었음.
1
2
3
4
5
6
7
for(auto &sum: s){
    for(int i=K; i>=0; i--){
        for(int j=1; j<=sum.size()&&i+j<=K; j++){
            dp[i+j] = max(dp[i+j], dp[i]+sum[j-1]);
        }
    }
}
  • dp[i]: i권 팔았을 때 매입 가격의 최댓값
  • for의 i가 정방향이면 계속 앞의 가격을 참조를 해서 같은 책만 담는 경우가 있어서 역방향 해야 함.
    • 딴 이유가 있을텐데 나는 이렇게 이해하는게 그나마 맘에 와닿더라…..

#1058 친구 [S2]

링크

1
2
3
4
5
6
7
for(int k=0;k<N;k++){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            a[i][j] = min(a[i][j], a[i][k]+a[k][j]);
        }
    }
}
  • 그냥 플로이드 워셜 돌려서 a[i][j]<=2인 것의 개수를 세면 됨.
  • 첨에 초기화 잘 해야 함!


2022/01/18 화요일

2611 자동차경주 [G2]

링크

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
queue<int> q;
q.push(1);
while(!q.empty()){
    auto now = q.front();
    q.pop();
    if(now==1 && indeg[1]==0) break;
    for(auto [next, w]: adj[now]){
        indeg[next]--;
        if(dp[next] < dp[now]+w){
            dp[next] = dp[now]+w;
            befo[next] = now;
        }
        if(indeg[next]) continue;
        q.push(next);
    }
}
  • 위상정렬
  • dp처럼 하면 됨
  • befo[next] = now로 간 길 흔적 남겨서 나중에 트레킹 하면 됨


2022/01/19 수요일

1
exit(0)

python에서 exit(0)과 같음


2022/01/20 목요일

#19577 수학은 재밌어 [P2]

링크

  • $x\phi(x)=N$을 구해서 하면 된다
  • $\phi(x)/x$는 대략 $1/1.8*loglogn$


2022/01/21 금요일

#13900 순서쌍 곱의 합[S4]

링크

  • (1, 2, 3, 4)라고 하면
  • 1의 차례에서 1*(2+3+4)이고
  • 2의 차례에서 2*(3+4)이고
  • 3의 차례에서 3*4이니깐
  • 이걸 그대로 구현하면 됨

#2226 이진수[G4]

링크

  • dp[0]=1, dp[1]=0, dp[2]=1
  • dp[i] = dp[i-1]+2*dp[i-2] (i>2)

#7453 합이 0인 네 정수[G2]

링크

  • 파이썬에서 dict사용
    • c+d의 모든 경우를 거기다 집어 넣음(sum이라 하자)
    • -(a+b)가 sum에 있을 때 그 개수만큼(sum[-(a+b)]만큼) 답을 더해준다.
  • C++에서 map했는데 터졌는데 unordered_map했는데도 터진 나와 아슬아슬 성공한 실버 선생님


2022/01/22 토요일

#1049 기타줄[S4]

링크

  • 6개로 이루어진 가격과 1개로 이루어진 가격을 각각 오름차순으로 정렬
  • 거기서 가장 싼 1개짜리를 v1, 6개짜리를 v6라고 하면
    • v1*6 <=v6 이면 그냥 그대로 가는거고
    • 아니면 최대한 v6을 많이 가져가는 방향으로 나아감

#2812 크게 만들기[G4]

링크

  • 스택으로 st.top()보다 현재 수가 크면 빼고 집어넣음


2022/01/23 일요일

prev
# PS # solved.ac # Daily BOJ
next