Neo Ground

PS에 뒤늦게 발들인 화석은 파릇파릇한 23, 24학번과 UCPC 예선을 치렀다.예선에서는 그냥 대충 기대만큼의 그렇게 높진 않은 성적을 받았는데... 본선 진출 순위가 후했다. 그래서 예선에서 탈락할 것 같던 우리 팀도 본선에 진출하게 되었다. 본선날이다. LG전자... 여기도 좋은 곳이지. 보내주시면 감사히 절하고 갑니다. 대회장에서 네트워크 설정도 하라고 한다. 사실 네트워크 세팅도 내가 안 했고 내용을 글 쓰는 지금도 안 읽어봐서 왜 하는지 모른다.자리도 팀 별로 정해져 있다. 이런 친구도 하나씩 준다. 대회가 끝나고 메를 좋아하는 아는 사람에게 넘겼다. 이런 봉인된 봉투를 팀별로 나눠준다. 여기 안에 대단한 것이 들어 있다.문제 풀이가 시작되었다. 괴수들이 모여서 몇 분 지나면 바로 퍼스트 솔브..

30193번: 마술 도구샤레롱은 실버가 생각한 $0$ 이상 $N$ 미만의 정수를 맞추는 마술을 하려고 합니다. 이를 위해 샤레롱은 카드 $K$장을 준비해, 각 카드에 $0$ 이상 $N$ 미만의 서로 다른 정수를 $T$개 쓸 것입니다. 실www.acmicpc.net문제사실 지문부터 조금 난해했다. 최대한 간단하게 설명하면, $K$장의 카드에 정수를 각각 $T$개씩 작성하려 한다.정수들은 $0$ 이상 $N$미만 이고 하나의 카드에 적힌 정수들은 서로 다르다.그리고 $0\le a$N$이 주어지고 $K$를 최소화하고자 할 때 최소의 $K$와 그 방법을 출력하여라. $T$는 최소화 하지 않아도 된다. 음... 더 어렵나? 간단하게 작성하기가 영 쉽지 않다. 아이디어문득 어릴 때 본 마술이 떠올랐다. 마술의 해법은..

31248번: 3+1 하노이 탑 3+1 하노이 탑 게임은 가로 방향으로 일렬로 놓인 4개의 기둥과 크기가 서로 다른 $N$개의 원판을 이용한 게임이다. 편의상 왼쪽에 있는 기둥부터 차례대로 A, B, C, D라고 하자. 처음에는 기둥 A에 www.acmicpc.net 아이디어 D 기둥에 있는 원판은 다시 옮길 수 없다는 게 핵심적인 제한 요소인 것 같아 보인다. 그 말은 D 기둥은 무조건 가장 큰 원판부터 쌓아야 함을 의미한다. 이를 위해 $N$개의 원판에 대해 다음과 같은 과정을 떠올렸다. 제일 큰 원판 두 개를 제외한 나머지 원판 $N-2$개를 D를 제외한 빈 기둥 중 아무 곳으로 옮긴다. 두 번째로 큰 원판을 D를 제외한 빈 기둥으로 옮긴다. 제일 큰 원판을 D로 옮긴다. 두 번째로 큰 원판을 D로..

31003번: 언젠가 정렬이 될 수 있으면 좋겠네. $N$개의 양의 정수로 이루어진 수열 $A = [A_1, \cdots, A_N]$가 주어진다. 당신은 원하는 만큼 다음 조작을 할 수 있다. 조작을 하지 않는 것도 가능하다. 수열에서 인접한 원소가 서로소일 때, 그 두 원 www.acmicpc.net 문제 양의 정수로 $N$개로 이루어진 수열을 인접한 원소끼리 순서를 변경하여 사전 순으로 가장 앞에 오게 정렬하여라. 단, 인접한 원소가 서로소일 때만 순서를 변경할 수 있다. 아이디어 처음에는 버블 정렬과 유사한 방식을 떠올렸다. 첫째 원소부터 반복하며 현재 원소가 앞의 원소보다 작고 순서를 변경할 수 있다면 순서를 변경하고 이를 가능할 때까지 반복한다. 하지만 이런 방식은 문제가 있다. [4 2 3]은..

24731번: XOR-ABC 주어진 조건을 만족하는 $(A,B,C)$ 쌍의 개수를 $1\,000\,003$으로 나눴을 때 나머지를 출력한다. 단, $1\,000\,003$은 소수이다. www.acmicpc.net 문제 $K$자리 이진수 $A, B, C$가 $1\leq A

18789번: 814 - 2이 출력된 표에서는 1부터 112까지 읽을 수 있지만, 113은 읽을 수 없어 112점을 받는다.www.acmicpc.net 요약 및 후기수작업 -> 표 전체 무작위 생성 코드 작성 -> 표 일부 무작위 수정 및 개선 -> 보조 점수 metric 추가 -> 성공 결과적으로 문제를 해결하는데 성공했지만 효과적인 방법은 아닌 것 같다. 원래 이 분야가 그렇다지만 이렇게 하면 좋을까?라는 생각으로 무한한 실험을 하는게 썩 똑똑하게 풀었다는 생각은 들지 않는다. 그래도 독특한 문제 스타일을 경험해서 재밌었고 첫 루비 문제 해결이라 뿌듯하다.아이디어 1: 수작업처음에는 수작업으로 0부터 9까지 고르게 채워넣어 8*14의 표를 완성하였다. 나름 괜찮게 배치하였다고 생각했지만 점수는 200..

11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 $n$번 째 피보나치 수를 $10^9+7$로 나눈 나머지를 구하여라. $n$은 $10^{18}$보다 작거나 같은 자연수이다. 아이디어 $n$이 매우 크다. 단순하게 기본적인 피보나치 재귀 함수를 구현해서는 불가능하다. 따라서 다음과 같이 생각해 보았다. 1. 일반항을 통해 구하기 -> 일반항에 $\sqrt 5$가 포함되어 계산이 간단하지 않다. 점화식에 포함된 제곱을 분할정복을 사용한다 하더라도 많은 제곱을 할 수록 부동소수점의 오차가 쌓일 것이다. -> 불가능 2. 점화식을 통한 분할정복을 통해 구하기 -> $f(2n)=g(f(n),..

2549번: 루빅의 사각형첫 번째 줄에는 움직이는 횟수를, 두 번째 줄부터는 한 줄에 하나씩 타일을 움직이는 방법을 순서대로 출력한다. 이때, 격자판의 i번째 행을 k칸 움직였다면 정수 1과 i와 k를 빈칸을 사이에 두고www.acmicpc.net문제4*4의 격자판의 각 타일에 1부터 16까지의 숫자가 적혀있다. 행을 밀거나 열을 밀어서 격자판의 숫자를 순서대로 정렬할 때 그 최소 이동 수와 이동 경로를 출력하라.아이디어15퍼즐이 생각나는 문제이다. 15퍼즐은 IDA* 알고리즘을 이용해 그나마 빠른 속도로 해결할 수 있다.또한 15퍼즐은 각 이동의 소요 비용이 1이므로 IDA* 알고리즘에서 우선순위 큐를 사용할 필요가 없다.이 문제도 IDA* 알고리즘을 적용할 수 있을 것 같아 보인다.관건은 휴리스틱 함..