- boj 19525 ac, 다4
어려웠지만 의도한대로 잘 풀려서 다행이였다.
나는 조건을 그리드에서 어떤 직사각형을 그리든, 직사각형의 네 꼭짓점중 적어도 1개에는 . 이 있어야 한다고 해석했다.
결국 n=150 이라는 제한된 그리드에서 직사각형을 최대한 많이 집어넣는게 목표가 되었기 때문에 단순히 그리디하게 접근해서 개형을 분석해보자는 생각에 그리디로 방향을 잡았다. 패턴을 찾기까지 꽤 오래 걸렸는데, 정사각형에서 왼쪽 아래 꼭짓점을 제외한 나머지 점들이 x+1, y-1 씩 이동할 때 그리는 자취를 보면 된다. 서로 다른 대각선이여도 결국 같은 열에 존재하는 순간이 올텐데, 그때만 아래로 한 칸씩 이동해가면 기울기?가 오묘하게 다른 대각선들을 계속 그릴 수 있다. 풀고 나서 태그를 봤을 때 정수론 태그가 달려있는게 이해가 가지 않았는데.. 다른 분들을 보니 모듈러 산술로 증명한 풀이가 정해인 것 같아 뭔가 찜찜한 기분이다.
- boj 31439 pac, 플1
n을 몇가지 조건으로 나누어 각 조건마다 일반화 시키려고 시도했으나, 장렬하게 실패했다. 혹시 무작위화로 푸는건 아닐까 하고 시도했으나 n=100으로 테스트했는데 vscode가 에러메시지로 욕해서 그만뒀다. 에디토리얼을 살펴봤는데, 그토록 도전했던 일반화가 정해로 나와있었다.. 분해서 괜히 틀린 부분이 없나 혼자서 검증해본뒤 구현해서 제출했다.
어째서 pac인가? 라고 한다면 나도 모르겠다.. 코드 자체도 너무 간단한데다가 출력 방식만 바꿨는데 pac를 받는 %가 달라지는 기적을 경험했다. 구현 방법을 바꾸니까 또 %가 달라진다. 아니 다 똑같은 로직인데.. 알고리즘 이랄것도 없고 그냥 식 계산해서 수열 출력하는건데..
