풀이 (A ~ F)
[#A]
A번 문제는 단순한 문제다.
특정 수열이 주어지면 2가지 작업을 수행할 수 있다.
한 가지 작업은 위치를 재배열 하는 것이고, 나머지 작업은 특정 범위안의 수에 -1을 곱하는 것이다.
이때, 두 작업을 수행한 뒤 수열의 합의 최댓값을 구하면 되는 문제다.
수열의 합이 최댓값이 되기 위해서는 모든 수가 음수가 아닌 양수가 되면 된다.
그러므로 위치를 재배열 할 때 음수들이 전부 붙어있게 재배치하고, 그 범위에 -1을 곱하면 전부 양수가 되므로, 결과값은 모든 배열의 수의 절댓값을 더한 값과 같다.
[#B]
B번 문제는 특정 수열이 주어졌을 때, 모든 수들을 더하고 3으로 나뉘는지 확인한다.
만약 3으로 나누어지지 않는다면 특정 작업을 수행해 0이 되도록 만들고, 그때 시행한 작업의 최소 횟수를 계산하는 문제다.
여기서 3으로 나눴을 때, 0이 되지 않는다면 수행할 수 있는 작업이 두가지 있다.
1. 특정 수를 선택하고 1을 더하기
2. 특정 수를 삭제하기
여기서 중요한 점은 수열의 합을 3으로 나눴을 때, 나머지가 1인 경우가 핵심이다.
나머지가 0이라면 작업횟수가 0이다.
나머지가 2라면 1번 작업으로 바로 나머지를 0으로 만들어 줄 수 있으므로, 최소 작업 횟수가 0이다.
나머지가 1일 경우는 약간 다른데, 수열에 있는 수 중에 나머지가 1인 수가 있다면 그 수를 빼서 나머지를 0으로 만들 수 있다.
그러므로 수열의 합을 3으로 나눈 나머지가 1일 때, 수열에 나머지가 1인 수가 있다면 작업횟수가 1이다.
만약 나머지가 1인 수가 없다면, 특정 수에 1을 더하는 작업을 두번해야하기 때문에 작업횟수가 2다.
[#C]
이 문제는 k의 고유한 값을 구하는 문제다.
$$l = k*a^x*b^y,\, (x>=0, y>=0인\, 정수)$$
위 조건을 만족할 때, a와 b l이 주어진다면 k에 들어갈 수 있는 수들을 구하면 된다.
단순하게 set을 이용하면 쉽게 풀 수 있는 문제다.
l을 a로 계속 나눠 나머지가 0이 아닐 때 까지 몇 번 나눠야 하는지 횟수를 구한다.
마찬가지로 l을 b로 계속 나눠 나머지가 0이 아닐 때 까지 몇번 나눠야 하는지 계산한다.
이후 각각 몇번 나눌 수 있는지 횟수를 구했다면, 2중 for문을 돌려 a와 b의 값을 횟수만큼 증가시킨다.
(즉, a^x와 b^y에 들어갈 수 있는 x와 y의 범위를 구하고, x와 y의 범위만큼 for문을 돌리는 것이다.)
이제 x와 y범위를 구했으므로, for문으로 l을 (a^x*b^y)로 나누었을 때, 나머지가 0이라면 set에 추가한다.
set으로 중복을 제거했으므로 최종적으로 set에 들어있는 원소의 개수를 출력하면 된다.
[#D]
특정 수열이 주어지고, 이 수열의 배치를 내가 원하는대로 할 수 있다.
그리고 mod연산을 연속적으로 수행해 나머지가 0이 아니도록 할 수 있는지를 구하는 문제다.
이 문제는 나머지 연산의 특징을 생각하면 쉬운 문제다.
크기가 다른 어떤 수 x와 y가 있다고 가정하자, 이때 x < y 라는 관계가 성립한다면 항상 y로 x를 나눴을 때, 나머지는 x가 되게 된다. (y의 나머지 범위 0 ~ (y-1)이다.)
그러므로 수열을 오름차순으로 배치하게 된다면, 가장 작은 수가 몇 개 있는지에 따라 위치를 바꿔 나머지가 0이 아니게 되게 할 수 있는지 계산할 수 있게 된다.
만약 가장 작은 수 a가 1개 있다고 가정하자.
그러면 가장 작은 수보다 큰 수들은 a를 나누면 나머지가 무조건 a가 되기 때문에 0이 아니게 만들 수 있다.
만약 가장 작은수 a가 2개 이상 있다면, a로 수열의 수들을 나눠 나머지가 0이 아닌 경우가 있는지 확인한다.
만약 나머지가 0이 아닌 경우가 있다면, a보다 작은 나머지를 만들 수 있으므로 나머지가 0이 아니게 만들 수 있다.
나머지가 0이 아닌 경우가 없다면, 모든 수가 a의 배수라는 뜻이므로, 나머지가 0이 아니게 만들 수 없다.
[#E]
이 문제는 n개의 수를 가진 수열 a가 주어지고, a 수열의 시작 범위 index인 l과 특정한 수 u가 주어진다.
이때, 수열의 r을 (l <= r <= n) 정할 수 있다.
r을 정했다면,
$$k\, = \, a_l\, +\, a_{l+1} ...\, a_r$$
$$PerformanceScore\, =\, u+(u-1)+(u-2)\, ... \, +(u-k+1)$$
을 계산하고 PerformanceScore(이하 score)가 최대가 되는 r을 계산하는 문제다.
이 문제의 핵심은 u에 있다. score에 더해주는 값이 음수가 될 수 있으므로, score가 최대가 되려면 k가 u와 같거나 u+1인 경우가 최대다.
하지만, a의 값을 더해서 k를 만들기 때문에 r을 잘 선택해도 항상 k의 값이 u와 같지 않다.
그러므로 u와 최대한 가까운 수가 되는 k를 찾는게 핵심인 문제다.
여기서 u와 가까운 수가 되는 k를 찾을 때, k는 a_l ~ a_r을 더한 값이다.
여기서 r을 정하고 k를 계산한 다음 u와 비교해야 하는데, 누적합을 이용하면 r을 정하면 한번의 계산으로 k를 구할 수 있다.
이제 u와 가까운 수가 되는 k를 찾는데, l부터 n까지 전부 for문을 돌리는 방법은 비 효율적이다.
누적합을 이용하기로 했으므로, r이 증가할수록 누적합도 증가하는 오름차순 수열이다. (즉, 정렬이 되어있는 상태다)
그러므로 이분탐색을 이용해 u와 가장 가까운 범위의 k값을 찾으면 된다. (만약 u와 떨어진 거리가 같은 값이 여러개라면, 더 작은 r값을 return한다.)
[#F]
이 문제는 돌을 피해서 (0, 0)에서 (m-1, n-1)에 도달할 수 있는지 구하고, 도달 할 수 있다면 가장 빠른 이동 횟수를 구하는 문제다.
특징은 지각변동으로 인해 내가 한 칸 움직일 동안에 돌은 위로 한칸 움직인다는 것이다.
또한, 위와 아래가 연결돼 있어 맨 위로 올라간 돌은 다시 아래서 나온다.
+ 왼쪽방향으로 이동 불가
처음에는 아무 생각 없이 time에 따라 돌의 위치들을 전부 저장하고, BFS로 탐색을 했다.
하지만, 메모리 초과로 인해 이 방법은 불가능 했다.
그래서 생각한 방법은 위로 움직이는 이동을 제거한 방법이다.
어차피 위로 이동하는 것은 돌과 위치를 비교했을 때, 가만히 있는 것과 다름이 없다.
그렇기 때문에 오른쪽과 아래쪽으로만 움직인다고 가정을 했다.
그리고 메모리 초과를 줄이기 위해 돌의 위치는 그대로 둔 visited를 하나 이용했다.
그리고 돌이 가만히 있다고 가정하면 로봇이 아래로 이동하는 경우는 아래로 두칸 이동하는 것과 같으며, 오른쪽으로 이동하는 경우는 아래로 한칸 이동하고 오른쪽으로 이동하는 경우와 같다.
이렇게 탐색하는 코드를 구현했다.
그리고 현재 로봇이 (m-1, y)에 도달한 경우 탐색을 멈췄다.
왜냐하면 로봇이 아래로 이동한다고 가정하고 탐색을 했지만, 실제로는 위로 이동할 수 있고, 위와 아래가 연결되어 있기 때문에 위로 움직여서 n-1에 도달할 수 있기 때문이다.
그러므로 실제 로봇의 y축 위치는 (y+n-(이동한 시간%n))%n이다.
(돌 대신 로봇이 항상 아래로 한 칸씩 움직인다고 가정했으나, 실제로는 돌이 이동했기 때문에 위치를 정정해주어야 한다.)
이제 실제 로봇의 y축 위치를 기준으로 위로 이동해서 (m-1, n-1)에 도달하는게 빠른지 아래로 이동해서 도달하는게 빠른지 비교하고, 최솟값을 구한다.
그리고 현재까지 구한 (m-1, n-1)에 도달하는데 걸린 최솟값과 비교해 더 작은 값을 저장한다.
((m-1, n-1)이 아니라 (m-1, y)에 도달하는 경우에 탐색을 멈췄기 때문에 전부 비교해야 한다)
최종적으로 구한 가장 작은 값을 출력하고 만약 방문이 불가능하면 -1을 출력하면 된다.