엘릭시르제

문제 링크: 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번의 삼각형의..

문제 링크: 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

문제 링크: https://www.acmicpc.net/problem/24417 24417번: 알고리즘 수업 - 피보나치 수 2 코드1 코드2 실행 횟수를 1,000,000,007로 나눈 나머지를 한 줄에 출력한다. www.acmicpc.net 문제 풀이 dp를 이용해서 피보나치 수를 구하면 된다. 너무 웰노운인 문제다. 코드 파이썬 코드 C++ 코드