Daily BOJ 22/02/03-22/02/12
2022/02/12 # PS # solved.ac # Daily BOJ

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



BOJ 1000 solve! 🥳

BOJ 1000 solve
2022/02/02 14:35

  • 설을 맞이해서 무작정 우다다다 달렸다.
  • 막판에는 JOI 브론즈 문제를 골라 풀었지만 그 전에는 그래프 뽀개기의 이름 하에 온갖 그래프, 특히 다익스트라 문제 풀고, 조합론 문제를 풀면서 머리를 많이 굴렸다.
  • 내부 검수자를 할 수 있는 조건이 되었다!
  • 그 때 푼거는 나중에 정리하고 일단 그 이후에 천천히 문제를 푼 것에 대해서 정리하도록 하겠다.


2022/02/10 목요일

#9935 문자열 폭발[G4]

링크


2022/02/11 금요일

#15686 치킨 배달[G5]

링크

1
2
3
4
5
6
7
8
9
int ans = INF;
int K = ck.size();
int check[15] = {0};
for(int i=K-M; i<K; i++) check[i]=1;

do {
    ans = min(ans, cal(check));
} while(next_permutation(check, check+K));
cout << ans;
  • next_permutation사용
  • 치킨집 K개 중 M개를 선택해서 그것에 대해서 계산식을 진행


2022/02/12 토요일

#1007 벡터 매칭[G2]

링크

벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다.

1
2
3
4
5
6
7
vector<int> v;
for(int i=0; i<N/2; i++) v.push_back(0);
for(int i=0; i<N/2; i++) v.push_back(1);

do {
    ans = min(ans, cal(v));
} while(next_permutation(v.begin(), v.end()));
  • $n \choose \frac{n}{2}$인 상황에서 선택된거 계산
  • $\frac{n}{2}$는 좌표를 더하고 나머지는 좌표를 밴다

#1937 욕심쟁이 판다[G3]

링크

  • 팬더를 어느 지점에 놓았는지 다 놓고, 그 때 얻을 수 있는 값들 중에서 가장 최대값이 정답
  • 그냥 다 열심히 계속 구하면 시간 초과 무조건 날 것이기 때문에 현재 상태를 저장할 수 있는 것이 필요함
    • dp[x][y]: (x, y)에서 이동할 수 있는 칸의 최대 개수
    • dp[x][y]: 기본값은 1
  • 그러고 DFS 돌리면 될 듯. BFS를 가지고 완전 탐색하기엔 얘도 시간 초과로 예상이 들어가지고
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int solve(int x, int y){
    if(dp[x][y]!=-1) return dp[x][y];
    
    dp[x][y] = 1;
    for(int k=0; k<4; k++){
        int nx = x + dx[k];
        int ny = y + dy[k];
        if(isOut(nx, ny)) continue;
        if(a[x][y] < a[nx][ny]) {
            dp[x][y] = max(dp[x][y], solve(nx, ny)+1);
        }
    }
    return dp[x][y];
}
prev
# PS # solved.ac # Daily BOJ
next