엘릭시르제

A. Card Game Contest (백준 14551)조합론 각각의 덱은 독립적이므로 총 방법의 수는 $A_1$부터 $A_N$까지 곱하면 된다. 단, 덱이 없을 수도 있는데, 이때는 스킵하거나 0을 1로 바꾸면 된다. $M$으로 나눈 나머지를 구해야 하므로 곱할 때마다 모듈러 연산을 취해주면 된다.  B. 행사장 대여 (Small) (백준 14732)구현 범위가 작으므로 좌표를 받을 때마다 그 부분의 영역들을 2차원 배열에 1로 채워주면 된다. 이후 넓이를 구할 때 1의 개수를 세어주면 된다. C. 체크포인트 달리기 (백준 29891)그리디, 정렬 일단 들어오는 모든 수가 양수 혹은 음수일 때를 생각해보면, $N$이 $K$의 배수라면 거리가 먼 순서부터 체크하던지, 가까운 순서부터  체크하던지 상관없지..

31472번 - 갈래의 색종이 자르기 31472번: 갈래의 색종이 자르기첫 번째 줄에 정수 $W$가 주어진다. ($2 \le W \le 20\,000$, $W$는 짝수) 항상 답이 존재하는 경우만 입력으로 주어진다.www.acmicpc.net 1회 양갈래 컵 A번 문제다. 가장 쉬운 문제인만큼 풀이도 쉽다. 원래 사각형의 절반 $W$가 주어지므로 2를 곱한 후 제곱근 해주면 한 변의 길이가 된다. 단, 출력할 때 정수로 출력하는 것을 잊지 말자. 이것 때문에 틀리신 분들이 조금 존재했고, 예제만 보시고 /3*4 하신 분들도 많았다. 여담으로 이 문제는 원래 점이 여러 개 주어지고 컨벡스 헐을 구한 후 반으로 나누고 컨벡스 헐 내부에 있는 점들이 반으로 나눈 선분의 왼쪽에 있는지 오른쪽에 있는지 판별하려는..

문제 링크: https://www.acmicpc.net/problem/9011 9011번: 순서 n개의 정수로 된 순서 S= (s1, s2, ..., sn)가 있다. 여기서 si ≠ sj이고, 1 ≤ si ≤ n이다. S로부터 새로운 순서 R = (r1, r2, ..., rn)을 얻을 수 있는데, 여기서 ri는 S의 부분 순서 {s1, s2, ..., si-2, si-1} 중에서 www.acmicpc.net 문제 풀이 구현 R 수열의 뒷부분부터 처리하면 어렵지 않다. 처리는 R[i]+1을 중심으로 하면 된다. 가령 R수열의 마지막은 오른쪽 부분이 없고 왼쪽에는 자신보다 작은 수의 개수이므로 R[i]+1로 자명하다. 그렇다면 중복 혹은 자신보다 작은 수가 오른쪽에 있는 경우는 어떻게 해야할까? 예제 1을 ..

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

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