$n$과 $k$가 주어지면 $n$개의 아무 수를 더 해서 $k$의 배수를 만들고 싶은데, 그 $n$개의 수중 가장 큰 수의 값을 가장 작게 만들고, 그 수를 구하는 문제다.
$n$보다 $k$가 작으면 성립하지 않으므로 $n$보다 크면서 가장 작은 $k$의 배수를 구해준다.
$n$개의 수를 모두 1로 맞추면 $n$이 나오고, $n+1$은 1,1,1,1.....2, $n+2$는 1,1,1,1.....2,2, $n + (n - 1)$은 1,2,2,2,2....2 이므로 $t*n + alpha$에 대해 $alpha == 0$이면 $t$이고 $alpha != 0$이면 $t + 1$이다. $t*n + alpha = k$를 계산해주면 된다.
매 달의 물건의 가격을 나타내는 배열 $a_n$이 주어진다. $i$번째 달의 가격상승률은 $a_i / sum(a_0 ~ a_{i-1})$일때 각 달의 물건의 가격을 적절히 증가시켜서 매 달의 가격 상승률을 $k$이하로 만들려할 때 전체 가격증가의 최소 값을 구하는 문제다. 설명만 보면 어려우니 예제를 보는게 더 이해하기 쉽다.
각 가격상승률 공식을 정리해보면 $100 * a_i \leq k * sum$이 만족해야한다. 만약 이 조건을 만족하지 못 한다면, $sum$을 최소한으로 늘려서 만족시키게 해야한다. $sum$을 늘리는 작업은 사실상 $a_0$의 가격을 계속 증가시키는 것과 동일하다. 예제에는 $a_0과 a_1$의 가격을 증가시켰지만, $a_0$의 가격만 99 올린다고 생각하는게 더 생각하기 쉽다.
$100 * a_i \leq k * (sum + alpha)$가 만족하는 최소 $alpha$를 구해주면 된다.
문제설명은 패스. 직접 예제를 보는게 훨씬 이해하기 쉽다.
greedy로 풀다가 dp로 전향했다.
$dp[i][0] = (c[i] - 1) + (b[i] - a[i] + 2)$,
$dp[i][1] = (a[i] != b[i] ? max(dp[i - 1][0], dp[i - 1][1] -(b[i] - a[i]) + (c[i] - 1 + 2)), 0)$
이다.
$dp[i][0]$의 경우 기존의 cycle을 무시하고, 새로 cycle을 만들어 나가는 경우다.
$dp[i][1]$의 경우 기존에 cycle에 $i$번째 철사를 연결하여 cycle을 만들어 주는 경우인데, $a[i] == b[i]$이면 무조건 새로 cycle을 만들어야 한다. 반대의 경우 기존에 cycle에 철사 연결이 가능하므로 연결해준다.
새로 cycle을 만들어주는 경우는 결국 $dp[i][0]$이므로 그냥 0으로 처리해주어도 무관하다.
전체 dp table의 최대값이 정답이다.
greedy로 풀릴 문제인데 맞왜틀?때문에 시간을 너무 많이 날려서 끝나기 직전에 dp로 전향하여 풀었다. 그래서 dp테이블 정의가 이상한데, 조금만 고치면 greedy로 해결가능하다.
$n + 1$개의 마을과 한 방향으로만 이동이 가능한 $n$개의 도로가 각 마을에 연결되어 있다. 그런데, 한 도로를 따라서 다른 마을로 이동할 때마다 모든 도로의 방향이 뒤집어진다. 각 마을에서 출발하여 도착할 수 있는 최대 마을의 개수를 구하는 문제다. 같은 도로를 여러번 오갈 수 있다.
조금만 생각해보면 같은 도로를 여러번 오갈 수 있지만, 그런 경우는 정답에 영향을 미치지 않는 다는걸 알 수 있다. 각 마을에서 이동을 edge로 표현하면 indegree = outdegree가 되므로 degree가 2의 배수가 되어 각 마을에서 도로의 상태는 이동 경로와 무관하다는 걸 알 수 있다.
dfs로 풀 수 있으나, 코드가 길어질 느낌이 들어서 dp table 2개 만들어서 풀었다. $dp1[n]$은 각 마을에서 오른쪽으로 갈 수 있는 최대 도로 수, $dp2[n]$은 각 마을에서 왼쪽으로 갈 수 있는 최대 도로 수로 정의하면 각 마을에서 이동할 수 있는 마을의 수는 $dp1[i] + dp2[i - 1] + 1$이다.
$dp1[i] = (s[i] == R ? (1 + (s[i + 1] == L ? dp[i + 2] + 1 : 0 )) : 0)$이고,
$dp2[i] = (s[i] == L ? (1 + (s[i - 1] == R ? dp[i - 2] + 1 : 0 )) : 0)$이므로 간단하게 풀린다.
$C$번 문제에서 너무 시간을 많이 잡아먹어서 $D$번을 5분정도 밖에 못 봤는데 5분 본 것만으로 풀이가 생각난 것 보니 많이 쉬운문제였던듯 하다.
