Neo Ground

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

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

11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 문제 N*N개의 격자 구조의 방이 있고 각 방에는 다른 방의 불을 켤 수 있는 스위치가 있다. 불이 켜져 있으면서 현재 위치한 방에서 상하좌우로 인접한 방만 이동할 수 있다. 유일하게 불이 켜져 있는 방인 (1,1)의 방에서 출발할 때 불을 켤 수 있는 방의 수의 최댓값을 구하여라. 아이디어 및 구현 격자 모양에서 구조에서 인접한 방을 탐색하려면 당연히 BFS를 떠올리지 아니할 수 없다. 하지만 ‘불을 켜는 방..

9363번: 큰 나눗셈 이론물리학자들은 '삶, 우주, 그리고 모든 것'에 대한 질문의 궁극적인 해답이 42라고 생각하지 않았다. (은하수를 여행하는 히치하이커를 위한 안내서 中 한 내용) 대신 양의 정수 A와 B를 나눈 www.acmicpc.net 문제 두 수 $A$, $B$의 인수들 $A_1, A_2, ..., A_n$과 $B_1, B_2, ..., B_n$이 주어진다. 주어진 인수를 통해 $\frac{A}{B}$를 기약분수 형태로 나타내어 출력하여라. 아이디어 각 인수의 최댓값은 100만이다. 100만까지의 소수를 미리 구해놓는 것이 좋을 것 같다. (총 78498개) 인수들의 개수는 최대 22만개이다. 단순히 이들을 모두 곱한다면 당연히 연산 가능한 수를 벗어나므로 인수들을 모두 소인수분해하여 두 ..

16209번: 수열 섞기 인접한 원소의 곱들을 최대화한 본 수열의 재배열을 하나 출력하자. 만약 최대화할 수 있는 재배열이 여러 가지 있다면 아무거나 하나 출력하면 된다. www.acmicpc.net 문제 길이가 $N$인 수열 $a_1,…,a_N$을 재배열 했을 때 인접한 원소의 곱들의 합, 즉 $a_1a_2+a_2a_3+…a_{N-1}a_N$이 최대일 때의 재배열 된 수열을 출력하여라. 아이디어 직관적으로 절댓값이 큰 수부터 서로 곱해야 합을 최대로 만들 수 있음을 알 수 있다. 양수는 양수끼리, 음수는 음수끼리 곱하여 최대한 많은 곱을 양수로 만들어야 한다. 0은 최대한 0끼리 곱하고 부득이한 경우 절댓값이 가장 작은 수와 곱한다. 구현 주어진 수열을 정렬한 후 음수, 0, 양수 부분으로 분리한다. ..