Neo Ground

24526번: 전화 돌리기 아이디어문제를 단방향 그래프로 표현할 수 있다.어떤 부원이 두 번 이상 전화를 받게 되려면, 그 부원이 어떤 사이클에 존재해야 한다.더불어 사이클에 존재하는 부원들에게 전화를 넘겨줄 수 있는 부원들과, 그 부원들에게 넘겨줄 수 있는 또다른 부원들과, ... 재귀적으로 이런 부원들은 잠재적으로 어떤 부원이 두 번 이상 전화를 받게 할 수 있다.반면, 그렇지 않은 부원이 다시 사이클에 진입 시킬 수 없는 부원이고 아래 그래프에서는 6, 7, 8번 정점에 해당한다. 구현6, 7, 8번 정점과 같은 정점을 찾자.DFS와 유사한 방식으로 자식의 리턴값을 이용해서 구현할 수도 있다. 하지만 훨 간단한 방법이 있다.모든 정점의 자식의 수(혹은 out edge의 개수)를 관리한다.자식의 수가..

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),..