인피니티스톤의 색깔이 입력으로 들어오면 앞으로 더 모아야하는 인피니티스톤의 이름을 출력하는 문제다.
넘어가자.
$x$와 $y$가 주어진다. $x^y$와 $y^x$의 값을 비교해야하는 문제다. $1 <= x, y <= 10^9$이다.
$x$와 $y$가 작은 어떤 특정한경우 이외에는 모두 지수값이 큰 수가 더 크다. 그 특정한 경우는 $x$나 $y$가 1이거나 $x$와 $y$가 (2,3) 또는 (3,2)인 경우 또, (2,4), (4,2)인 경우다. 그 외 모든 경우에 대해서 $x$가 크면 $x^y$보다 $y^x$가 크고 $y$가 크면 $y^x$보다 $x^y$가 크다.
또 다른 풀이로는 log를 취하여 비교하는 방법이 있다.
처음에는 이거 너무 어려운거 아닌가? 생각했는데 다들 쉽게 풀길래 무슨 방법이 있지 생각하다가 지수가 크면 더 크다는 점과 몇몇 예외가 발생한다는 점을 발견하고 제출했다. (4,2)가 되는 경우를 노트에 적어놓고 예외처리를 안 하는 바람에 한번 틀렸다.
코드를 깔끔하게 하려면 x,y가 계산할 수 있을 만큼 충분히 작은 값이면 pow 때려버리고, 큰 값이면 위에 서술한대로 처리해주면 된다.
$n$개의 전광판이 있고, 그 전광판마다 쓸 수 있는 글씨의 크기와 전광판광고의 가격이 주어진다. 3개의 전광판을 차례로 선택하는데, index가 커질수록 전광판의 글씨크기도 커져야한다. 즉, $i < j < k$에 대해 $s_i < s_j < s_k$이어야한다. 이때 전광판광고 가격의 최소가격을 구하는 문제다. 글씨크기는 커지기만하면 된다.
O($n^2$) lis같이 구해버리면된다. $dp[i][j]=min(dp[next][j + 1] + c[i]), \, (s[next] > s[i])$가 점화식이 된다.
어이없게 1번 틀렸는데 $s$와 $c$같이 축약된 이름으로 배열을 짜서 $s$와 $c$가 헷갈렸다. 점화식에서 $c[i]$를 더 해주어야하는데 $s[i]$를 더해주는 바람에 한번 틀렸다.
$n$개의 마을에서 특산품 박람회를 여는데, 각 마을에는 1개의 특산품만 갖고 있다. 박람회를 열려면 $s$개의 특산품을 갖고 있어야하는데, 특산품은 이웃마을에서 공수해 올 수 있다. 모든 마을은 다른 마을로 경로를 따라 이동할 수 있다. 박람회를 열기 위해 각 마을에서 다른 마을에서 공수해 올 때드는 최소비용을 구하는 문제다. 도로의 cost는 모두 1이다.
$dist[n][k]$ $:$ $n$번째 마을에서 $k$번 특산품을 얻기위해 움직어야하는 최소비용 으로 정의해보자. $k$번 특산품을 갖고 있는 마을을 queue에 모두 넣은 뒤 bfs를 돌면 모든 마을과의 최소비용을 O($k*(n + m)$)으로 구할 수 있다.
풀이는 짧고 간단한 문제지만 생각이 조금 어려웠다. C번 문제가 dp인데다가 최소비용을 구한다길래 dp로 접근했고, 점화식도 쉽게 나오고 예제도 다 맞게 나왔지만 제출하자마자 틀렸다. 문제가 cycle이 생기는 경우인데 양방향이라 cycle이 무조건 생기게 되어있으며, 양방향에 의한 cycle을 없애려 parent를 dp테이블에 추가하면 시간초과가 되므로 불가능하다. 게다가 테이블을 채우는 함수를 호출하는 순서에 따라 테이블의 값이 달라져버린다. 그래서 dp로는 문제를 풀 수가 없다.
$1, 2, 3 .... n$으로 순서대로 있는 순열이 있는데 petr는 이 순열의 랜덤으로 다른 두 값을 $3n$번 swap하고, Um_nik은 $7n + 1$번 swap한다. swap을 하고 난 결과가 주어졌을 때 누가 swap한 건지 출력하는 문제다.
이걸 어떻게 알아내야하는가 싶지만 잘 보면 petr의 swap 횟수가 짝수면 Um_nik은 홀수고, 홀수이면 짝수다. 다시 말해, $n$이 홀수일 때는 petr는 홀, Um_nik은 짝이며 짝수일 때는 petr는 짝, Um_nik은 홀이다.
이제 죽어진 순열이 홀수번 swap했는지 짝수번 swap했는지 알아내야하는데, $1, 2, 3, ... n$의 순열을 주어진 순열로 바꾸는데 걸리는 최소 swap횟수를 세어야한다. 반대로 말하면 주어진 순열을 $1, 2, 3, ... n$의 순열로 바꾸는데 걸리는 최소 swap횟수를 세어야한다. 이 횟수는 주어진 배열의 cycle의 개수로 알 수 있다. 예제의 2 4 5 1 3을 보면 1 -> 2, 2 -> 4, 5 - > 3, 1 -> 4, 5 -> 3 으로 graph를 만들 수 있고, (1, 2, 4) 와 (3, 5)가 사이클을 이룸을 알 수 있다. cycle내에서는 cycle의 크기 - 1 만큼 swap하면 정렬된 순열을 만들 수 있으므로 $n - 사이클의 개수$가 최소 swap횟수이다.
최소 swap횟수를 알았으면 petr인지 Um_nik인지 알 수 있는데, 사이클의 개수 $k$라 하고, 먼저 $n$이 홀일 때를 보자. $k$가 홀 이면 $n - k$는 짝 이므로 Um_nik이다. $k$가 짝 이면 $n - k$는 홀 이므로 petr이다. $n$이 짝일 때 $k$가 홀 이면 $n - k$는 홀 이므로 Um_nik이다. $k$가 짝 이면 $n - k$는 짝 이므로 petr이다. 따라서 $k$, cycle의 개수만 세어주면 petr인지 Um_nik인지 판단할 수 있다.
D번 풀닥 안 풀려서 봤는데 딱 보니 $3n$과 $7n + 1$이 서로 짝이면 홀이고 홀이면 짝을 갖길래 아 홀짝문제구나 생각했는데 어떻게 최소swap을 구하는지 생각이 안 나서 넘어갔다. cycle을 이용해서 구한다는 점도 신박하지만 segment나 mergesorted tree로도 풀린다니 어떻게 풀어야하는지 생각해보아야겠다.
==== 추가
꼭 최소swap횟수를 구하지 않아도, 그냥 아무렇게나 swap횟수 구해서 홀, 짝을 나누어도 된다. segment로 풀려면 arr[i]기준에서 i보다 작은 index를 가지고 arr[i]보다 큰 녀석들을 세어서 모두 더하면 된다. 예제의 2 4 5 1 3을 보면 0 0 0 3 2 가 되고, 합은 5이다. 이 합이 $n - k$이므로 $n$에 따라서 경우를 나누어 주거나 $(n) xor (n - k) = 1$ 임을 이용하여 출력하면 된다. 이 합을 naive하게 구하면 O($n^2$)이므로 segment로 풀어주면 O($nlogn$)에 풀린다. 입력으로 arr[i]가 들어올 때 마다 index arr[i]에 값 1을 add하는 update를 해주고 [arr[i] + 1, n)사이의 구간합을 구하는 query를 보내면 합을 구할 수 있다. 유의할 점은 합이 int의 범위를 넘어가므로 long long을 써주어야한다. int로 커버가능할 줄 알고 제출했다가 14번 tc에서 틀리고 이렇게 푸는게 아닌가 싶어서 tc 500만개정도 만들어서 돌려봤는데 다 맞길래 보니 long long 문제다.. ㅠ
