엘릭시르제

문제 링크: https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 문제 풀이 너비 우선 탐색, 누적 합 BFS를 이용하는 건 그다지 어렵지 않다. 대부분의 BFS 문제처럼 직사각형의 왼쪽 가장자리를 기준으로 방문하지 않았다면 방문해주고 벽이라면 방문하지 않는 등 일반적인 문제랑 비슷하다. 하지만 직사각형 전체 중에 벽이 있다는 걸 확인하는건 어떻게 해야할까? 먼저 H*W번을 매번 방문할 때 마다 체크해준다? 딱봐도 시간 초과..

문제 링크: https://www.acmicpc.net/problem/4658 4658번: 삼각형 게임 삼각형 게임은 시작할때 여섯개의삼각형을 부여받는데, 각 변에는 숫자가 쓰여있다(그림 참고). 이 삼각형들을 돌리고 움직여서 육각형을 만들어야 하는데, 반드시같은 숫자가 쓰여있는 변끼리 www.acmicpc.net 문제 풀이 브루트포스 알고리즘 브루트포스로 대충 돌려서 풀었다. 테케가 몇 개인지 모르지만 한번 할때 $6!*3^{6}$ 정도니 시간 안에 들거 같다. 일단 삼각형을 입력받고 왼쪽 숫자는 0, 오른쪽 숫자는 1, 밑변 숫자는 2로 인덱스를 정하자. 다음 그림과 같다. 이런 삼각형이 주어졌을 때, 순서가 정해져있지 않기 때문에 순열을 이용해주고, i번의 삼각형의 1번 인덱스와 i+1번의 삼각형의..

22년 7월 31일 00시 29분에 브론즈 3을 올솔하면서 브5, 브4, 브3을 모두 올솔했다. 사실 별거없다. 왜냐하면 현존하는 문제 난이도 중에 다이아3 ~ 루비쪽을 제외하면 문제수가 적은 편이다. 거기다 방금 언급한 난이도는 ps쪽을 깊게 하지 않는 이상 절대 만날 일 없고 정말 어려운 문제이다. 하지만 브론즈 쪽은 간단한 구현과 굳이 알고리즘을 공부할 필요도 없이 해결할 수 있으며 코드 길이도 짧은 편이다. 기업에서 하는 대회나 코딩 테스트 쪽에서는 이런 브론즈를 대부분 0점 방지용으로 내니 정말 쉬운 문제가 아닐 수 없다. 그럼에도 불구하고 브론즈 3을 올솔을 한 이유가 있다. 왜 했는가? 그냥 심심했다. 왜냐하면 현재 플레티넘 4를 달성했는데, 티어에 비해 좀 못푸는 감이 있다. 그렇다고 새로..

문제 링크: https://www.acmicpc.net/problem/20412 20412번: 추첨상 사수 대작전! (Hard) 한 줄에 걸쳐 준표가 좋아하는 소수 m, 참가자들이 정한 Seed, 시연으로 공개된 X1, X2 이 주어진다. 항상 가능한 상황만 입력으로 주어진다. www.acmicpc.net 문제 풀이 페르마의 소정리 페르마의 소정리를 이용하여 풀었다. $(a \times Seed+c) \equiv X1 \;(mod \; m)$와 $(a \times X1+c) \equiv X2 \;(mod \; m)$를 빼서 한개의 연립합동방정식을 만든다. $a(Seed-X1) \equiv X1 - X2 \;(mod \; m)$가 되는데 m은 소수이고 0