4주차 연습 (2)

연습 (1) 에서는 solved.ac 기준 G5...G1 문제들을 다루고, 연습 (2)에서는 solved.ac 기준 P5...P3 문제들을 다룹니다.

https://www.acmicpc.net/problem/2242

2242번: 삼각형 만들기

풀이

두 변의 길이를 고정하면, 나머지 한 변의 길이는 쉽게 알 수 있습니다.

그렇기 때문에, $i, j$를 변으로 하는 삼각형을 만들 수 있는지를 $D_{i, j}$로 정의합니다. 이렇게 되면, 새로 $x$ 막대기가 들어왔을 때, $D_{i, j}$가 참이면 $D_{i+x, j}$와 $D_{i, j+x}$도 참으로 갱신해주는 방식으로 $D$를 계산할 수 있습니다.

 

코드: https://www.acmicpc.net/source/share/57e8e18836234f72a36aabb2a5202288

 

https://www.acmicpc.net/problem/4718

4718번: Not One Bit More

풀이

1이상 $H$미만의 $i$중에서, $K(i) = X$인 경우가 몇 개인지 세는 함수 $s(H, X)$를 만들게 되면 답을 $s(HI+1, x) - s(LO, x)$로 구할 수 있습니다. 이제 $s$를 찾아봅시다.

 

$N_1$은 항상 $60$이하의 값이 되기 때문에, 우리는 $N_1$이 어떤 값일 때, $K(N_0)$가 어떤 값인지 알 수 있습니다. 이를 이용해서 $K(N_0)$가 $X$가 되는 $N_1$을 고정시켜놓고, $H$미만의 $N_1$이 몇 개 있는지를 셀 수 있습니다.

$2^w \le H < 2^{w+1}$이라고 하면, $2^w$ 미만의 모든 수를 만들 수 있기 때문에, 여기서 이진수에서 $1$이 $X$번 등장하는 수는 조합을 사용하면 $w \choose X$로 구할 수 있습니다.

 

나머지 $2^w$이상 $H$ 미만의 수에 대해서는, $2^w$에 해당하는 비트가 항상 $1$이고 나머지 비트에 대해서는 $H - 2^w$ 이하이기 때문에, $H-2^w$미만의 수에서 $1$이 $X-1$번 등장하는 수의 개수와 똑같습니다.

이렇게 재귀적으로 수를 세어 주면, 답을 구할 수 있습니다. 생각해 주어야 하는 예외는 $K(1) = 0$이라는 것이고, $K(1) = 1$으로 고려해서 위의 로직을 실행 한 다음에, $1$인 경우 예외처리를 해 주는 것이 구현을 쉽게 할 수 있습니다.

 

코드: https://www.acmicpc.net/source/share/275e3f496c1643fb8c792ec1a5d7dee6

 

https://www.acmicpc.net/problem/7036

참고: https://www.acmicpc.net/problem/2184

7036번: Grazing on the Run

풀이

풀의 위치를 정렬한 이후에 생각합시다. 최적의 해에서 소가 뜯어먹은 풀의 위치는 연속되어 있습니다. 어떤 시점을 기준으로 그 전에 소가 방문한 위치는 연속된 선분으로 나타나고, 소가 풀의 위치에 방문하면 해당 풀을 먹지 않을 이유가 없습니다. 그렇기 때문에 풀이 자라는 연속된 구간에 관해서 최적의 답을 생각해야 한다는 것을 알 수 있습니다.

 

어떤 시점에서 $i$번째부터 $j$번째까지 풀을 모두 뜯어먹는 동안 구간 안에서 풀이 썩은 정도를 $X$, 풀을 모두 뜯어 먹는데 걸린 시간을 $Y$라고 합시다. 이 이후에 나머지 ($i$ 미만 혹은 $j$ 초과) 풀 중 $x$번 풀을 $t_x$시간 이후에 뜯어먹는다고 한다면, 총 풀이 썩은 정도는 $X + \sum (Y + t_x)$ 입니다. 여기서, $Y$는 $x$와 관련 없는 상수이기 때문에, 밖으로 빼내 주면, $X + (N-(j-i+1))Y + \sum t_x$가 됩니다. 이제 $\sum t_x$를 최소화 하는 문제가 되었고, 이는 $X, Y$와 무관한 값입니다. 즉, 매 순간에서 $X + (N-(r-l+1))Y$를 최소화 해 주면 되는데 이는 뜯어먹지 않은 풀에 대해서도 썩은 정도를 함께 고려해서 최소화 하는 것과 같습니다.

 

어떤 시점에서 $i$번째부터 $j$번째까지의 풀을 모두 뜯어 먹었다면 그 직후 소의 위치는 $P_i$ 혹은 $P_j$입니다. 두 경우에 대해서 $(i, j)$의 상태를 $(i, j-1)$과 $(i-1, j)$에서 가져오면 문제를 풀 수 있습니다. 이 때 이동 비용은 이동거리에다가 남아있는 풀의 수를 곱한 값입니다.

 

코드: https://www.acmicpc.net/source/share/cc420354b1d145b790a0abf6da4e8b1b

 

https://www.acmicpc.net/problem/7117

7117번: Sevens, twos and zeros

풀이

수 $x$의 뒤에 $7, 2, 0$을 붙이면 $(10x + 7), (10x+2), (10x)$가 됩니다. $x$를 $n$으로 나눈 나머지가 $m$이라고 한다면 뒤에 $7, 2, 0$을 붙인 수를 $n$으로 나눈 나머지는 $(10m+7) \bmod n, (10m+2) \bmod n, (10m) \bmod n$이 됩니다.

 

$m$을 $(10m+7), (10m+2), (10m)$으로 바꾸는데 자릿수가 하나 늘어납니다. 수의 $m$의 상태를 $m$을 $n$으로 나눈 나머지로 해서 그래프를 만들면 $0$ 이상 $n$ 미만인 $m$에 대해, $m$에 서 $(10m+7) \bmod n, (10m+2) \bmod n, (10m) \bmod n$으로 향하는 간선이 있습니다. 이 그래프에서의 경로는 수를 만드는 과정이며, 그 때 경로의 최종 상태(끝점)은 만들어진 수를 $n$으로 나눈 나머지입니다.

 

우리는 자릿수가 가장 작은 답을 찾아야 하기 때문에 한 번 바꾸는 과정을 비용 $1$이라고 생각하면, 결국 문제는 $2 \bmod n$과 $7 \bmod n$에서 시작해서 $0$으로 돌아오는 가장 비용이 작은 사이클을 찾는 문제가 됩니다. 이는 BFS로 풀 수 있고, 사전순으로 최소가 되는 것을 찾기 위해서는 BFS에서 $0, 2, 7$순으로 정점을 큐에 넣어주면 됩니다.

 

코드: https://www.acmicpc.net/source/share/8143533047694b87864b52dc91116153

 

https://www.acmicpc.net/problem/8226

8226번: Vouchers

풀이

$a_k$명으로 구성된 모임은 $a_k$의 배수 위치의 티켓만 가져갈 수 있습니다. 또한, $a_k$명으로 구성된 모임이 마지막으로 가져간 티켓이 $i \cdot a_k$라는 의미는, $a_k, 2a_k, \cdots, (i-1)a_k$번 티켓을 모두 가져갔다는 뜻입니다.

이를 이용해서 각 구성된 모임의 사람 수에 따라서 마지막으로 가져간 티켓 번호를 저장해 주면, 이 티켓 번호는 계속 증가합니다. 또한, 우리가 신경써야 하는 티켓 번호($b_k$의 최댓값)가 $X$이라고 하면 그 이후의 티켓 번호에 대해서는 무조건 선물을 가져갈 수 없기 때문에 무시하면 됩니다.

 

답은 $a_k$에 대해서 $\frac{X}{a_k}$번만 증가하기 때문에 $a_k = 1, \cdots, Y$에 대해서 티켓 번호를 모두 저장해도 티켓 번호가 총 $O(X \log Y)$번만 증가하게 되며(harmonic sum), 티켓을 가져갔는지 아닌지와 상품권이 들어있는지 등에 대한 처리를 번호 하나에 대해 $O(1)$에 처리할 수 있으므로, 총 시간복잡도는 $(N+M+Y+X \log Y)$가 됩니다.

 

코드: https://www.acmicpc.net/source/share/06d08407160c4e69be9f859399422ff1

https://www.acmicpc.net/problem/8311

8311번: Variable Subsequences

풀이

$i$번째 수로 끝나는 좋은 variable subsequence의 개수를 $D_i$라고 합시다.

 

$i$번째 수 하나만 존재하는 경우를 제외하고는, $i$번째 수 바로 직전의 수를 $j$번째라고 하면, $j < i$이고 $a_j \ne a_i$를 만족해야합니다. 즉 $D_i = 1 + \sum_{j<i, a_j \ne a_i} D_j$이고, $a_j \ne a_i$를 따로 빼면, $D_i = 1 + \sum_{j<i} D_j - \sum_{j<i, a_j = a_i} D_j$가 되며, 이는 각 수에 대해 현재까지 등장한 합을 관리해주는 것으로 문제를 해결할 수 있습니다.

 

코드: https://www.acmicpc.net/source/share/3188bd42a2e7408bb5aada3d4986fe19

 

https://www.acmicpc.net/problem/12341

12341번: Fair and Square (Large2)

풀이

어떤 수 $x$가 팰린드롬이고 그 수의 제곱수 $x^2$도 팰린드롬인 조건을 생각해 봅시다. 첫 자리수가 마지막 자리수와 같아야 한다는 것을 생각하면, 다음과 같은 결론을 얻을 수 있습니다.

• $x$의 일의 자리수를 제곱했을 때 두 자리수가 되면 안됩니다.
  • $x$의 일의 자리수가 $4$이상인 경우에는, 가장 앞에 등장하는 수는 $16, 25, 36, 49, 64, 81$이 됩니다. 이 수는 모두 일의 자리수와 십의 자리수(즉, $x^2$의 가장 앞 수)가 다르며 받아올림이 일어난다고 해도 마찬가지입니다.
• $x^2$의 십의 자리를 계산할 때 받아올림이 일어나면 안됩니다.
  • $x$의 일의 자리수를 제곱했을 때 한 자리수이므로, 받아올림이 일어나면 $x^2$의 첫 자리에 $1$이 더해지게 되어 마지막자리와 달라지게 됩니다.

이 논리를 계속 따라가 보면, $x^2$의 모든 자리에서 받아올림이 일어나면 안 된다는 사실을 알 수 있습니다.

이를 이용해서 모든 길이가 $50$이하인 $x$에 대해서 백트래킹을 해도 정답을 찾을 수 있습니다. 구현을 좀 더 쉽게하는 방법은 다음 사실을 이용하는 것입니다.

• $x$가 $N$자리 수 일 때, $x^2$의 $N$번째 자리에서 받아올림이 일어나지 않으면, 모든 자리에서 받아올림이 일어나지 않는다.
  • 이는 재배열 부등식을 통해 증명할 수 있습니다. $x^2$의 $N$번째 자리의 경우가 $x$에서 서로 반대대는 위치끼리 곱해지는 위치인데, $x$는 팰린드롬이므로 같은 수끼리 곱하는 것이 되며, 이 때 해당 자리가 최대가 됩니다.

코드: https://www.acmicpc.net/source/share/f025ba27da964c50977cb5e00725b569