[BOJ 23814] 백준 23814번 - 아 저는 볶음밥이요
1. 문제
$23814$. 아 저는 볶음밥이요 (2021 POSTECH Programming Open Contest B번)
백준 23814번 - 아 저는 볶음밥이요 (https://www.acmicpc.net/problem/23814)
2. 풀이
원래 $K$는 짜장면, 짬뽕, 볶음밥 중 하나를 선택하는 수이지만, 볶음밥의 최대 개수를 구해야 하므로 $K$전체가 볶음밥을 선택했다고 둔다.
만약에 $K$에서 $D$명이 $N$으로 옮겨간다고 생각해보자. $(D \leq K라고 가정) \, N,\, M,\, K\, $ $-> N+D,\, M,\, K-D$ 이때, 얻을 수 있는 군만두의 수는 $N/D,\, M/D,\, K/D $ $\rightarrow (N+D)/D,\, M/D,\, (K-D)/D $ $ = N/D+1,\, M/D,\, K/D-1$ 로 전체 군만두 양의 변화가 없다. 따라서 $K$에서 $N$이나 $M$으로 $(0\sim D-1)$개만큼 옮겨가는 것만 의미가 있다.
$(0\sim D-1)$개가 $K$에서 빠지게 되면, $K$로부터 얻을 수 있는 군만두의 양이 그대로이거나 $1$개가 줄어든다. 따라서, $N$이나 $M$에서 볶음밥을 $1$개 더 얻을 수 있게 되어야 옮기는 의미가 있다. 이는 $N$이나 $M$을 $D$의 배수로 만들어야 한다는 것이다.
여기서 군만두의 개수를 최대로 하는 ‘볶음밥의 최대 개수’를 구해야 하므로, 볶음밥 또한 최대한 덜 옮겨야 한다. ($N$이나 $M$을 딱 $D$의 배수로 만드는 데에 그친다.)
이를 종합하여 보면, $N$ 또는 $M$을 그들 각각에서 (그들보다 큰) 가장 가까운 $D$의 배수로 만들면 된다. 여기서 네 가지 경우의 수를 생각해볼 수 있다.
- 볶음밥을 아예 옮기지 않는 경우
- $N$을 $D$의 배수로 만드는 경우
- $M$을 $D$의 배수로 만드는 경우
- $N$과 $M$ 둘 다 $D$의 배수로 만드는 경우 (코드 24줄)
이들 각각의 경우에 대해서 얻을 수 있는 군만두의 수를 계산하여 최댓값을 갱신한다. 군만두의 개수를 최대로 하며 볶음밥을 최대로 만들어야 하므로, 군만두 값이 더 크면 볶음밥 수는 무조건 갱신, 군만두 값이 같으면 볶음밥 수는 최댓값을 찾아야 한다.
3. 채점 결과
4. 회고
군만두 수의 변화 가능성에 대해 알기까지, 수많은 예제 케이스들에 대해서 값을 빼고 더하며 결과값이 어떤 식으로 변화하는지를 관찰하고 분석했다. 덕분에 제대로 된 방법을 알기까지 무려 40분이나 걸렸다.
문제의 핵심을 바로 캐치해낼 수 있는 능력을 좀 더 길러야겠다는 생각이 들었다. 틀린 건 $D$값을 $D$로 안 두고 예제 그대로 $3$으로 둬서 틀렸었다.
댓글남기기