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