2/20
- boj 14939 ac, 플4
칸에 대해 꺼진 경우와 켜진 경우를 완탐하려면 으로 말도 안 되는 걸 알 수 있다. 2가지 아이디어가 필요한데,
- 모든 전구는 0번 또는 1번만 누른다.
- 전구를 누르는 순서는 상관없다.
전구가 꺼지고 켜진 횟수에 따라 전구의 상태가 결정된다는 걸 토대로 위 두 가지 아이디어를 모두 얻을 수 있다.
이후에는 전구의 1행에 대한 경우만 으로 완탐해주면 되는데, 2행 이후에는 1행에 전구를 켜고 끌 방법이 없기 때문에 2행에선 무조건 1행 전구를 모두 끄는 방식으로 해야 하기 때문이다.
일반화하면 전구 는 전구 가 꺼져 있으면 누르지 않고, 켜져 있으면 눌러서 꺼주는 방식으로 구현하면 된다.
- boj 22412 ac, 골2
역추적으로 에 있는 모든 ABC를 A, B, C 중 하나로 바꾸는 과정을 반복하여 'ABC'에 도달할 수 있는지 확인하면 된다.
약간 까다로운 조건이 하나 있는데, ABC를 로 치환하여 생긴 문자열 에 대해 을 구성하는 문자열이 3종류가 아니라면 는 변환 불가능하다. 그리고 바꿨을 때 없는 문자열로만 변환 가능하다. 예를 들어 ABABC라는 문자열에서 ABC를 A로 변환하면 ABA가 된다. 하지만 ABA에서 A를 ABC로 변환하면 ABCBABC로, 역이 성립하지 않는다.
- boj 8111 ac, 플5
모듈러 연산만 잘 적용하면 빠르게 bfs로 풀린다. 0을 붙이는 건 , 1을 붙이는 건 로 풀자.
질문 게시판에 올라와 있는 글이 충격적이었는데, 전처리로 풀 생각을 어떻게 하셨을까.. ㄷㄷ
- 솔브닥 다이아 달성
프로필에 티어바가 파란색으로 보이는 게 어색하기만 하다.
요즘은 AC 레이팅이 아니라 프로필에 보이는 찌그러진 팔각형을 채우기 위해 부족한 부분의 문제만 팠던 것 같은데, 어째 다이아를 달성했지만 팔각형은 여전히 찌그러져 있다..
원래 부족한 부분이었던 그리디, 그래프, 기하 부분에 대한 얘기를 잠깐 하자면
그리디: 다른 거 없이 순수하게 그리디 아이디어만으로 풀어야 하는 문제는 대개 최적의 값을 결정하는 기준을 찾는 게 굉장히 어려운 편이다.
그 기준이 왜 최적의 값인지 증명도 해야 하고, 엣지 케이스에 잘못 걸려 무수히 많은 wa를 받는 일도 허다하다. 그럼에도 그리디는 산전수전 다 겪으며 해를 찾아냈을 때의 기쁨이 남다르다. 고난도일수록 더 그렇다. 쓰러지지 않는 보스의 약점을 찾아낸 것 같달까. 그리고 그리디 문제를 많이 풀수록 그 '기준'이란 것의 틀이 대충 보이게 된다. 보자마자 '어 이거 그리디 같은데?' 하는 직감을 가지는 것만으로도 굉장히 성장한 것 같아 기분이 좋다.
그래프: js로는 트리를 구현하는 게 까다로운 편이다. 그래서 그래프 문제를 처음 풀 때에는 그런 함수와 class 한 무더기를 미리 준비해놓고 풀어야 하는 게 진입 장벽이었다. 오죽하면 PS를 시작하고 얼마 안 되었을 때는 bfs가 그렇게 어려워서 메모장에 적어 외울 때까지 보고 다녔었던 기억이 있을 정도. 그럼에도 익숙해지면 이것만큼 날먹인 게 또 없다. 특히 세그먼트 트리를 처음 알았을 때의 그 놀라움이란..
기하: 🤮
찾아보니 왜인지는 모르겠지만 기하 태그만 보면 도망가는 기하기피자 분들이 꽤 있다. 필자도 기하기피자 중에 한 명인 것 같다.
알고리즘도 CCW와 컨벡스 헐밖에 모르는 상태이기 때문에 랜디 할 때도 기하 태그는 빼고 풀 정도이다.
기하가 가장 문제인 만큼, 기하와 좀 친해지려고 23459번 같은 문제를 장기 프로젝트로 잡고 열심히 풀고 있으나... 노코멘트.
다이아지만 아직도 오목팔각형을 보유한 필자는 스스로를 부끄럽게 여긴다. 열심히 하자..!
댓글