기록(記錄)

본문 바로가기

알고리즘

백준 문제 풀이 [Python] 7538번 Incomplete chess boards (추후 보강 예정) https://www.acmicpc.net/problem/7538 25/06/09 유명한 퍼즐 문제이다. 간단하게 구현만 하면 되는 문제로, 이걸 정당화하는데에는 조금 어려운 내용이 들어간다. 문제 접근 방식: 주어진 요구 사항은, $8 \times 8$크기의 체스판이 주어지는데, 이 체스판의 두 곳에 구멍을 뚫어놓고, 남은 칸들을 $2 \times 1$크기의 도미노 타일로 전부 매울 수 있는지의 여부를 각 테스트 케이스마다 판단하는 것이다. 이 문제는 Mutilated chessboard problem이라는 이름으로 검색하면 위키에 잘 나와있다.https://en.wikipedia.org/wiki/Mutilated_chessboard_problem Mutilated chessboard proble..
백준 문제 풀이 [Python] 34019번 [G] Grounded Number https://www.acmicpc.net/problem/34019 25/06/05 찍어서 맞추기는 쉽지만 증명하기 어려운 애드 혹 문제다. 문제 접근 방식: 그냥 작은 케이스에 대해 나열 해보면, 짝수일때는 가능하고 홀수일때는 불가능하다는 걸 확인할 수 있다. 실제로 그렇게 제출하면 맞을 수 있는데, 이를 증명하는 건 쉽지 않다. 증명 과정은 다음과 같다. $i$번째 연산 과정 전의 수를 $n_i$라고 하자. $n_i - i = d_i$라고 정의하자. 만약 $n_i$에서 연산을 한 결과가 $+1$인 경우, 즉, $n_i$가 $i$의 배수인 경우, 다시 말해, $i$가 $n_i$를 나눌 때, 같은 이야기로, $i$가 $d_i + i$를 나눌때, 즉, $i$가 $d_i$를 나눌 때, $d_{i+1} =..
백준 문제 풀이 [Python] 1459번 걷기 https://www.acmicpc.net/problem/1459 25/06/13 무난 무난한 기하학 + 애드 혹 문제이다. 약간의 케이스워크가 있는데, 잘 정리하면 케이스워크도 쉽게 정리할 수 있다. 문제 접근 방식: 문제는 가로, 세로로 가는 데 걸리는 시간과 대각선으로 가는데 걸리는 시간이 따로 주어지고, 양수 좌표 $x, y$가 따로 주어질 때 $(0, 0)$에서 해당 좌표로 갈 수 있는 최단 시간을 출력하는 것이다. 결국 세가지 경우로 나뉜다. 1. 가로, 세로 움직임만 사용하여 가는 경우 2. $x = x_0, y = y_0$를 벗어나지 않는 선에서 대각선 움직임을 최대한 사용한 후 가로, 세로 움직임을 사용하여 가는 경우 3. 벗어나도 상관없이, 대각선 움직임을 최대한 사용하여 가는 경우..

수학

회고록

감상록

티스토리툴바