BOJ 1353 - 합과 곱
합과 곱
시간 제한 | 메모리 제한 |
---|---|
2 초 | 128 MB |
문제
음이 아닌 수의 리스트가 있을 때, 그 리스트에 있는 수의 합이 S이고, 곱이 P일 때, 만족하는 리스트라고 한다.
S와 P가 주어졌을 때, 가능한 만족하는 리스트의 크기중 최소를 출력한다. 리스트의 크기란 그 리스트에 있는 수의 개수를 말한다. 만약 그러한 것이 없다면 -1을 출력한다.
리스트에는 정수가 아닌 수가 포함될 수도 있다.
입력
첫째 줄에 S와 P가 주어진다. S와 P는 1,000,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 출력한다.
풀게 된 계기
이 문제를 풀 때까지만 해도 PS에 이렇게 깊이 빠질 줄은 몰랐습니다.
아니, 사실상 이 문제 때문에 PS에 빠지게 되었다 해도 과언이 아닐 것 같습니다.
저는 개인 Discord 서버에서 다른 분들이 BOJ 문제를 풀고 계시는 걸 보고 “나도 잠깐 찍먹이나 해 볼까?” 하는 생각이 들어 문제들을 몇 개 풀고 있었습니다. 그리고 문제의 저 채팅이 등장합니다.
플래… 멋있잖아요?
바로 풀러 달려갔습니다.
풀이 과정
일단 리스트의 크기를 n이라고 할 때, 리스트의 원소들을
문제의 조건에 따라 우리가 구해야 할 것은
를 만족하는
또한
위의 부등식에 따라 식을 정리해 보면,
…그래서 이제 저걸 어떻게 풀죠?
좋아요, 지오지브라는 신이며 이는 고구려 수박도에도 나와 있습니다.
사실
아무튼, 이제 개형을 알았으니 우리가 해야 할 것은, 그냥 f(n)에 1부터 값을 쭉 대입해보다가, 극대점을 지나면 종료하는 겁니다. 조금 짜치지만(?) 대충 값을 대입하다 보면, 극대점의 x좌표가 선형 탐색으로 충분히 탐색할만한 범위 내라는 것은 금방 알 수 있습니다.
오, 완벽한 풀이야..! 하고 구현했습니다. 계산 과정에서 숫자가 굉장히 커져서 C#의 BigInteger
도 사용했고요. C#이 확실히 이런 면에서는 편한 부분이 있습니다. 그리고…
사소한 문제들이 많이 있었지만, 좀 더 중대한 문제도 있었습니다. 대표적으로 S = 1, S = 2인 경우가 있었는데, 이 경우 극대점의 x좌표가 1보다 작아집니다. 그래서 이 경우는 가능한 모든 경우 ((S = 1, P = 1), (S = 2, P = 1), (S = 2, P = 2))인 경우에 대해 조건 분기로 따로 처리해주었습니다.
그리고…
맞았습니다!
미분해서 극대점 구하기
여하튼, 재미있게 푼 문제였고 푼 이후에도 탐구를 조금 더 이어나갔었는데, 이에 대한 내용은 언젠가 생각이 난다면 적어보도록 하겠습니다.