[백준 알고리즘][파이썬/Python] 1500번: 최대 곱

문제

시간 제한 : 2초, 메모리 제한 : 128 MB

 

세준이는 정수 S와 K가 주어졌을 때, 합이 S인 K개의 양의 정수를 찾으려고 한다. 만약 여러 개일 경우 그 곱을 가능한 최대로 하려고 한다. 가능한 최대의 곱을 출력한다.

 

만약 S=10, K=3이면, 3,3,4는 곱이 36으로 최대이다.

 

입력

첫째 줄에 두 수 S와 K가 주어진다. K는 20보다 작거나 같고, S는 100보다 작거나 같으며 K보다 크거나 같다.

 

출력

첫째 줄에 정답을 출력한다. 답은 9223372036854775807보다 작다.

 

입출력 예

 

제출 코드

s, k = map(int, input().split())

key = s // k

if s % k == 0:
    print(pow(key, k))
        
else:
    result = 1
    while k != 0:
        if s % k != 0:
            result *= key
            s -= key
            k -= 1
        else:
            result = result * pow(s//k, k)
            k = 0
            s = 0 # 사실 없어도 됨. 어차피 k가 0이라 다음 번 반복에서 종료되기 때문.
    print(result)

문제의 핵심

# 1

이건 솔직히 감으로 풀어서 맞은 것이라 핵심이 정확히 뭔지는 모르겠다. 하지만 감으로 풀 때 생각했던 근거는 있다. (하지만 수학적으로 왜 그렇게 되는 것인지는 전혀 모른다. 그냥 진짜 직감으로 풀었다.)

 

합이 S가 되는 K개의 양의 정수가 여러 조합이 나온다면, 그 정수들 사이의 편차가 가장 적은 조합이 최대곱을 만족시키는 조합이라고 생각했다. 이러한 근거를 생각해낸 까닭은, 그저 (1, 1, 8), (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 1, 7), (2, 2, 6), ... 이런 식으로 조금 써 보니 그런 것 같았기 때문이다.

* 혹시나 로직의 근거를 수학적으로 파악하고 싶으시다면 다른 분들의 블로그를 참고해주셔야 할 것 같습니다...^_ㅠ

 

라인 별 풀이

(1) line 3

k개의 정수 간 편차가 최대한 적으려면 key값이 필요하다고 생각했다. 이 key값을 가지고 로직을 계속 이어나갔다.

 

(2) line 5, 6 

만약 S가 K의 배수라면, 그냥 key값을 k승만큼 곱한 값이 답일 것이므로 다른 복잡한 과정 거칠 필요 없이 바로 끝내줬다.

(ex. S = 25, K = 5라면 최적의 정수 조합은 [5, 5, 5, 5, 5]이다.)

 

(3) line 9

결과값을 저장하기 위한 변수 result를 선언해줄 것인데, 특정 값을 곱해주면서 최종 output에 도달할 것이므로 시작을 1로 선언한다.

 

(4) line 10

while의 종료 조건문은 k가 0이 될 때로 지정한다.

 

(5) line 11 ~ 14

이 while문에서는 k를 계속 뺄 것인데, 만약 남아있는 k가 s의 약수가 아니라면, 조합 내에는 key값을 가진 정수가 하나 추가된다고 생각하자. 그렇게 되면 남은 s는 본래 s에서 key값을 빼야 하고, 조합에 정수를 하나 추가시켰으므로 k도 1을 빼준다.

 

(6) line 17 , 18

혹은 남아있는 k가 s의 약수라면, 남은 k는 모두 s//k라는 값의 정수가 되어 조합에 들어가게 된다. 그게 편차가 가장 적은 최선의 값이기 때문이다.

 

추가적인 테스트 케이스

이건 내가 너무 감으로 푼 감이 없잖아 있는데, 사실 감으로 풀면서 다른 테스트 케이스를 생각해봤다. 많은 테스트 케이스는 아니지만, 로직을 짜는 데에 큰 도움을 준 것은 사실이다. 그래서 그 테스트 케이스에 대한 결과도 아래에 정리해야 할 것 같다.

 

 

테스트 케이스 # 1 : S = 10, K = 3 (문제에서 주어진 입출력 예시)

최대곱을 만들 수 있는 정수 조합 = [3, 3, 4]

결과 : 3 * 3 * 4 = 36

 

 

테스트 케이스 # 2 : S = 10, K = 8

최대곱을 만들 수 있는 정수 조합 = [1, 1, 1, 1, 1, 1, 2, 2]

결과 : 1 * 1 * 1 * 1 * 1 * 1 * 2 * 2 = 4

 

 

테스트 케이스 # 3 : S = 10, K = 9

최대곱을 만들 수 있는 정수 조합 = [1, 1, 1, 1, 1, 1, 1, 1, 2]

결과 : 1 * 1 * 1 * 1 * 1 * 1 * 1 * 1 * 2 = 2

 

 

 

Source : https://www.acmicpc.net/problem/1152