<

PS/백준

[백준] 겨울방학 동안 1일 1플래티넘 문제 풀기 도전기

leedongbin 2024. 3. 18. 04:17

어느덧 새싹 10단계 뱃지를 향한 여정도 얼마 남지 않은 가운데, 브실골 문제들만 풀며 스트릭을 연명하던 중 변화를 주기 위해 시작했던 혼자만의 챌린지가 드디어 끝났다.

끝나고 보니 몇몇 문제들은 난이도가 G1으로 내려가 있는데, 아무튼 풀 땐 P5였다. (다이아도 몇 개 풀었으니 쌤쌤이다)

주차별로 풀었던 문제들과 한 줄 평을 기록하고, 재밌는 문제들은 빨간색으로 추천했다.

1주차 (12/18 ~ 12/24)

2주차 (12/25 ~ 12/31)

3주차 (1/1 ~ 1/7)

4주차 (1/8 ~ 1/14)

5주차 (1/15 ~ 1/21)

  • 막대기 (백준 8984, P5)
    해시맵에서의 dp. 처음 봤지만 어려운 건 아닌듯하다.
  • 초직사각형 (백준 21761, P5)
    왜 굳이 __int128을 쓰게 했을까..
  • 체스판 여행 1 (백준 16959, P5)
    그냥 시키는 걸 잘 하면 된다. 이것저것 연습용으로 좋은 듯.
  • 상남자 (백준 17267, P5)
    bfs가 이렇게도 변형될 수 있구나 싶었던 문제.
  • Sevens, twos and zeros (백준 7117, P5)
  • IQ Test (백준 18665, P5)
    나에겐 그저 믿음이 전부였던 문제. 43번이라는 숫자는 어디에서 왔을까..
  • 구간 합 최대 (백준 14706, P4)

6주차 (1/22 ~ 1/28)

  • 친구 팰린드롬 2 (백준 15271, P4)
  • XOR 도형 (백준 2893, P4)
  • MooTube (Gold) (백준 15586, P4)
  • 카드 배열 (백준 2534, D5)
    이때부터 갑자기 1일 1다이아를 하려고 했다. 무슨 생각이었을까..?
  • フクロモモンガ (Sugar Glider) (백준 10048, D5)
    dijkstra+아이디어만으로 D5가 된 문제. 이 아이디어는 왠지 나중에 어디선가 쓰일 것 같다.
  • Daruma Otoshi (백준 13283, P5)
  • Subset Sum (백준 19133, D5)
    방학 동안 푼 문제 중에 가장 재밌었다. priority queue의 크기가 $2k$를 넘기 전에 답을 찾는 방법이 존재한다.
  • 강강술래 (백준 2323, P1)
    난이도 기여를 보니 푸는 방법이 정말 다양하다. 간선이 충분히 많음을 잘 이용하면 되는 문제.
  • 친구 (백준 19702, D5)
    강강술래와 비슷한 문제.
  • 보물의 위치 (백준 1399, P5)

7주차 (1/29 ~ 2/4)

  • 보물 찾기 (백준 17489, P5)
  • Kings on a Chessboard (백준 11163, D5)
    bitmask dp를 쓰면 시간초과를 피할 수 없지만, 답은 로컬에서 직접 찾으면 된다.
  • バームクーヘン (Baumkuchen) (백준 15586, P5)
  • 점 칠하기 (백준 1409, P5)
  • 싼 비용 (백준 1144, D3)
    갑자기 새로운 알고리즘을 풀어보고 싶어서 골랐다. 좋은 글이 있어서 편하게 이해했다.
  • 등산 마니아 (백준 20188, P5)
  • 백업 (백준 1150, D4)
  • 로스팅하는 엠마도 바리스타입니다 (백준 15647, P5)
  • 유성 (백준 8217, D4)
    세그먼트 트리도 TLE, 이분 탐색도 TLE, long long마저도 overflow인 악질 문제이지만, 그래서 추천한다.
    펜윅 트리, 병렬 이분 탐색, __int128을 사용하면 된다.
  • Count the Bits (백준 16417, P5)
  • 찾기 (백준 1786, P5)
    kmp 기본 문제인데 그냥 해싱으로 날먹했다. 해싱으로 안 풀리는 kmp문제를 아직은 본적 없지만, 그런 문제가 있다고는 들었다.

*아래는 Kings on a Chessboard의 답을 찾기 위해 사용한 코드이다.

더보기 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;

unordered_map<int,ll> nx[1<<16],dp[1<<16];
void solve(){
    int x,y,k;scanf("%d%d%d",&x,&y,&k);
    if(x>y)swap(x,y);
    int me=1<<y,all=1<<(y+1);
    dp[0][0]=dp[me][1]=1;//좌표(0,0)이고, 나를 포함한 내 이전 y+1개의 상태가 j일때, 경우의수
    int mx=0;
    for(int i=0;i<x*y-1;i++){
        int cx=i/y,cy=i%y;if(cx%2==0&&cy%2==0)mx++;
        for(int st=0;st<all;st++){
            for(int cnt=0;cnt<=mx;cnt++){
                nx[st>>1][cnt]=(nx[st>>1][cnt]+dp[st][cnt])%mod;
                if(cy==y-1){
                    if(st&6)continue;
                    nx[(st>>1)|me][cnt+1]=(nx[(st>>1)|me][cnt+1]+dp[st][cnt])%mod;
                }
                else{
                    bool ok=1;
                    if(st&me)ok=0;
                    for(int b=0;b<3;b++){
                        if(b+cy==y)break;
                        if(st&(1<<b))ok=0;
                    }
                    if(ok)nx[(st>>1)|me][cnt+1]=(nx[(st>>1)|me][cnt+1]+dp[st][cnt])%mod;
                }
            }
        }
        for(int st=0;st<all;st++)dp[st]=nx[st],nx[st].clear();
        if(cy==y-2){
            for(int cnt=0;cnt<=mx+1;cnt++){
                ll ans=0;
                for(int j=0;j<all;j++)ans=(ans+dp[j][cnt])%mod;
                printf("a[%d][%d][%d]=%lld,",cx+1,y,cnt,ans);
            }
        }
    }
    for(int st=0;st<all;st++)dp[st].clear();
}

int main() {
    freopen("out.txt","w",stdout);
    int t;scanf("%d",&t);
    while(t--)solve();
    fclose(stdout);
}

8주차 (2/5 ~ 2/11)

9주차 (2/12 ~ 2/18)

  • Time is Mooney (백준 18316, P5)
  • Convex Hull (백준 4181, P5)
    개인적으로 볼록 껍질 기본문제보다 훨씬 까다로웠는데, 왜 같은 난이도인지 모르겠다.
  • 큐빙 (백준 5373, P5)
    이걸 풀고 나서 다니던 스터디 카페 밑에 있는 다이소에서 루빅스 큐브를 샀다. 큐브 공식을 몰라서 피젯토이처럼 쓰다가 유튜브 보고 배웠다.
  • 시험 (백준 27654, P5)
  • 환상의 듀엣 (백준 11570, P5)
  • 현상금 사냥꾼 김정은 (백준 10272, P5)
  • 노래방 (백준 12932, P5)
    환상의 듀엣이랑 완전히 똑같은 문제인데, 급한 일이 생겨서 스트릭 때우기용으로 썼다. 둘 중 하나는 언레되어야할듯.
  • blobfearful (백준 24503, P5)

10주차 (2/19 ~ 2/25)

  • L 모양의 종이 자르기 (백준 10805, P5)
    L모양의 종이를 자르면 (직사각형+L모양) or (직사각형+직사각형)으로 잘린다는 것을 이용하는 문제.
  • 트리와 쿼리 (백준 25402, P5)
  • 이진 트리와 수열 (백준 16160, D5)
  • 부분 염기서열 (백준 2020, P5)
  • 회전 테이블 (백준 2518, P5)
    구현은 좀 귀찮지만 재밌는 dp 문제다.
  • 제단 (백준 5626, P5)
  • 푸앙이와 별 (백준 24396, P5)
  • 경찰서 (백준 1506, P5)
    SCC를 까먹고 floyd-warshall로 풀었다. 이걸 풀다가 발견했는데, floyd-warshall의 삼중 for문에서 거쳐 가는 정점을 고르는 for문이 가장 바깥에 있어야 정답이고, 가장 안쪽에 있으면 오답이다. 이 문제에 그에 대한 반례가 없어서 랜덤 데이터를 2시간 동안 돌려봤는데, 반례를 아직 못 찾았다.

11주차 (2/26 ~ 3/3)

느낀 점

장단점은 확실히 있었지만, 나에게는 단점이 좀 더 컸던 것 같다.
우선 장점으로는, 플래티넘 문제를 많이 접하다 보니 방학 동안 봤던 코딩테스트 문제들이 체감상 쉬워졌고, 문제를 풀 때마다 얻어가는 잡지식들이 확실히 있었다. 그리고 어차피 해야 할 거, 그동안 어렵거나 귀찮아서 안 풀었던 문제들이나 써본 지 오래됐던 알고리즘들을 오랜만에 건드려보는 기회가 되었다.

단점은... 너무 힘들었다.
문제를 해결하는 데 걸리는 시간의 편차가 너무 크다보니, 하루 계획이 크게 망가지는 일이 많았다. 그리고 생각보다 "매일매일"이란 것은 쉽지 않았다. 급한 일이 생겼을 때 스트릭을 채우기 너무 힘들고, 미리 풀어둔다 해도 디버깅 없이 한 번에 맞힌다는 보장이 없었다. 오히려 이전보다 더 스트릭의 노예가 되어 살았던 것 같다.

1일 1플래도 습관이 돼서 아직 계속하고 있는데, 곧 중간고사 기간이 되면 그만두지 않을까 싶다.

저작자표시 비영리

'PS > 백준' 카테고리의 다른 글

[백준] 새싹10단계 뱃지 획득! 1024일간의 여정  (3) 2024.05.08
백준 다이아 2 달성! + 재밌었던 다이아 문제들 간단한 풀이 모음  (4) 2023.08.15

'PS/백준'의 다른글

  • 현재글[백준] 겨울방학 동안 1일 1플래티넘 문제 풀기 도전기

관련글

티스토리툴바