1/17

- boj 19525 ac, 다4

어려웠지만 의도한 대로 잘 풀려서 다행이었다.

나는 조건을 그리드에서 어떤 직사각형을 그리든, 직사각형의 네 꼭짓점 중 적어도 1개에는 .이 있어야 한다고 해석했다.

결국 $n = 150$이라는 제한된 그리드에서 직사각형을 최대한 많이 집어넣는 게 목표가 되었기 때문에 단순히 그리디하게 접근해서 개형을 분석해보자는 생각에 그리디로 방향을 잡았다. 패턴을 찾기까지 꽤 오래 걸렸는데, 정사각형에서 왼쪽 아래 꼭짓점을 제외한 나머지 점들이 $x + 1$, $y - 1$씩 이동할 때 그리는 자취를 보면 된다. 서로 다른 대각선이어도 결국 같은 열에 존재하는 순간이 올 텐데, 그때만 아래로 한 칸씩 이동해가면 기울기?가 오묘하게 다른 대각선들을 계속 그릴 수 있다. 풀고 나서 태그를 봤을 때 정수론 태그가 달려 있는 게 이해가 가지 않았는데.. 다른 분들을 보니 모듈러 산술로 증명한 풀이가 정해인 것 같아 뭔가 찜찜한 기분이다.

- boj 31439 pac, 플1

$n$을 몇 가지 조건으로 나누어 각 조건마다 일반화시키려고 시도했으나, 장렬하게 실패했다. 혹시 무작위화로 푸는 건 아닐까 하고 시도했으나 $n = 100$으로 테스트했는데 VS Code가 에러 메시지로 욕해서 그만뒀다. 에디토리얼을 살펴봤는데, 그토록 도전했던 일반화가 정해로 나와 있었다.. 분해서 괜히 틀린 부분이 없나 혼자서 검증해본 뒤 구현해서 제출했다.

어째서 pac인가? 라고 한다면 나도 모르겠다.. 코드 자체도 너무 간단한 데다가 출력 방식만 바꿨는데 pac를 받는 %가 달라지는 기적을 경험했다. 구현 방법을 바꾸니까 또 %가 달라진다. 아니 다 똑같은 로직인데.. 알고리즘이랄 것도 없고 그냥 식 계산해서 수열 출력하는 건데..