Neo Ground

13252번: 카지노 아이디어우선 최적의 전략이 무엇인지 알아내는 것이 중요하다.결론부터 말하면, 플레이어들이 영역에 칩을 최대한 고르게 베팅하는 것이 최적의 전략이다.사실 이게 왜 최적의 전략인지는 잘 모르겠다. 대충 맞는 것 같아서 풀었다... 풀다보니 이게 골드가 맞나 싶었다.수학으로 풀리는 건가 싶어 고민해 봐도 도저히 간단한 식으로 유도될 것 같지 않았다. 그러면 DP를 의심해 본다.(N, M, K)의 게임의 확률을 P(N, M, K)라 하면 적당한 p에 대해 (0P(N-(N//M), M, K-1)*p + P(N-(N//M+1), M, K-1)*(1-p)로 계산 된다.이렇게 재귀 DP를 굴리면 될 듯도 하다. 시간이 초과되지 않을까 의심됐지만 다른 방법이 안 떠올라 일단 구현을 했다. 구현위 설..

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]은..

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* 알고리즘을 적용할 수 있을 것 같아 보인다.관건은 휴리스틱 함..