$k$명의 사람이 각각 $n$개의 종이비행기를 접으려 하는데 종이 1장당 종이비행기 $s$개를 만들 수 있다. 한 묶음에 $p$개의 종이가 들어있는 묶음을 몇 묶음 사야 하는지 출력하는 문제이다. 단, 1장의 종이를 찢어서 두 사람에게 나누어 줄 수가 없다.
먼저 예제를 보자. $(k, n, s, p) = (5, 3, 2, 3)$이다. 장당 2개의 종이비행기를 만들 수 있고, 한 사람이 3개의 종이비행기를 접어야 하므로 한 명당 2개의 종이가 필요하다. 5명이므로 10개의 종이가 필요하게되고, 한 묶음당 3개의 종이가 들어있으므로 총 4묶음을 사야 10개의 종이를 구할 수 있다. 즉, (($n$보다 크면서 가장 작은 $s$의 배수 $*$ k) 보다 크면서 가장 작은 $p$의 배수 $/$ $p$)를 구하는 문제다.
식을 한 줄로 정리해보면 $(n / s + (n \% s ? 1 : 0)) * k / p + ((n / s + (n \% s ? 1 : 0)) * k \% p ? 1 : 0)$로 정리할 수 있다.
초6 수학익힘책에나 나올법한 문제지만 k, n, s, p 같이 의미없는 변수를 던져주다보니 생각이 꼬였던 문제다.
$n*n$크기의 맵에 크기가 $1 * k$인 배가 어딘가에 있다. 맵에 어떤 한 점을 딱 찝었을 때, 그 위치에 배가 있을 확률이 가장 높은 위치를 출력하는 문제다.
정말 naive하게 배열을 모두 돌면서 $k$인 배가 들어갈 수 있으면 $n*n$짜리 sum배열에 ++해주는 식으로 O($n * n * k$)의 시간복잡도로 풀수 있다.
괜히 O($n * n$)에 풀려고 BOJ_N-ROOK문제 풀듯이 처리하다가 머리속만 꼬이고 WA 2번 받았다
$n$개의 사탕을 $k$명에게 나누어 주어야하는데 한번 나누어 줄 때 $x$개씩 똑같이 나누어 주고, 남으면 다시 $x$개씩 나누어 주는 방식으로 나누어 주어야한다. 나중에 $x$개 미만으로 사탕이 남았으면 그냥 버리고, $x$개씩 나누어주다가 중간에 멈추게되는 경우도 있다. $x$는 $M$이하 여야하며, 각 사람이 사탕을 받은 횟수는 $D$이하이여야한다. 이때 1번 친구가 최대로 받을 수 있는 사탕의 개수를 구하는 문제이다.
예를 들어, ($n, k, M, D$) = (20, 4, 5, 2)이면 $x$ = 4일 때 최대가 되는데, 4개씩 나누어주면 4명이 4개씩 받게되고, 사탕이 4개가 남는다. 사탕이 $x$개 이상 남았으므로 다시 4개씩 나누어 주어야하는데, 첫 사람에게 나누어 주고나면 0개가 되므로 멈추게되고, 첫 사람이 2번, 나머지 사람들은 1번씩 사탕을 받았으므로 $D$이하가 되서 조건을 만족한다.
답은.. 1~$D$까지 loop를 돌며 parametric search로 답을 찾아야한다. 시간복잡도는 O($DlogM$)이다.
개인적으로 정말 어려운문제라고 생각한다. 1위부터 10위까지 코드를 봐도 왜 이렇게 짰는지 이해가 안 될 뿐더러, 이해한 뒤 내가 직접짜서 돌려보니 안 돌아길래 debugging하는데만 3시간은 날렸다. 핵심은 parametric에서 $mid$값이 $M$을 넘으면 안된다는 점이고, 이걸 처리해주려면 decide함수의 반환이 t,f가 아니라 -1, 0, 1이여야 한다는 점이다.
그리고 문제의 난이도를 떠나서 기존에 내가 쓰던 형식화된 parametric search의 형식을 부수어준 문제일 뿐만 아니라 이전에는 나머지가 있으면 몫에 1을 더해주어야하는 계산을 할 때, 몫을 계산하고, 나머지를 계산해서 나머지가 0이 아니면 1을 더해주는 naive한 방식을 썼는데 다른 사람들 풀이를 보니 전부 [(제수 - 1) / 제수]로 처리해주는 것을 알았다. 보자말자 무릎부터 쳤다. 이거 너무 naive하지 않나? 싶으면 다른 사람 코드를 보자
개구리들이 $l$칸만큼만 $x$축으로 점프할 수 있다. 그리고 개구리들이 착지할 수 있는 돌은 한번 착지하면 가라앉는다. 각 $x$축위의 돌의 개수가 주어졌을 때 $w$위치까지 뛸 수 있는 개구리들의 마리수를 출력하는 문제다. ($w$위치는 땅이므로 돌이 없다)
입력으로 들어온 배열의 부분합을 구해서 크기가 $l$짜리 구간의 합의 최소값이 정답이다.
문제를 보자말자 아 이거 $l$만큼 점프 가능하니 $l$크기의 구간에서 최소를 구하면 되겠구나! 생각했다. 근데 $l$크기의 구간을 서로 겹치지않게 해야된다고 생각하는 바람에 첫 번째 예제에서 첫 5짜리 구간다음 남은 4짜리 구간을 어떻게 처리할까.. 생각하다가 이거 아닌갑다~ 하고 넘겨버렸다. dp는 절대 아닌것같고.. 어! 모든 개구리는 최대한 먼 돌에 착지해야 최적이구나 싶어서 greedy다 생각하고 lower_bound이용해서 O($nlogn$)에 풀려고 했는데 6번 tc에서 WA받아버렸다.
결국 못 풀었는데 솔루션보고 너무 허무했다. 컨디션이 안 좋을 수록 좀 더 생각해야겠다는 좋은 교훈하나를 얻었다.
