[1484] 다이어트

2023-02-23 | Algorithms / 백준 문제 풀이 모음 # Python, Sliver 3

백준 문제 풀이

1484번: 다이어트

이번 문제는 a^2 - b^2 공식인 (a+b)(a-b)를 이용해야한다.

• 해설

    성원이가 살이 쪘는데, 부끄러운 나머지 얼마나 쪘는지 안 알려주고
    a^2 - b^2 이런식으로 알려주었다...
    기존 몸무게도 모르기 때문에 위 공식에서 연립 방정식을 푸는 방식으로 진행해야한다.
      
    위 공식은 기존에 (a+b)(a-b)이다. a,b 양수라는 조건이 있기 때문에(몸무게니깐)
    a+b가 무조건 큰 수로 두고, 쪘다고 했으니 a^2을 찐 몸무게로
    인식하고 출력하면된다. 
      
    우선 연립 방정식으로 만들어야 하는데, 결과적으로 (a+b)(a-b)는
    입력 받는 G 값의 약수이기 때문에 추론이 가능하다.
      
    여기까지 풀이 과정을 정리하면 
    1. G의 약수를 찾는다.
    2. 약수에 맞게 a,b를 찾는다.
    3. a,b 가 양수인 경우 오름차순으로 출력하고,
     맞는 값이 없으면 -1을 출력한다.
      
    1. G의 약수 찾기
    약수를 찾는 것은 많은 방법이 있지만, 주로 가장 효율적인 방식은 제곱근 까지 나누어서
    0인 것을 약수로 두는 것이다. (약수에는 제곱근을 기준으로 대칭 으로 짝이 있기 때문에)
    하지만, 문제에서 해당 범위가 생각보다 적기 때문에 단순히 1~G까지만 체크했다.
      
    그것이 아래 코드이다.
    for i in range(1, G+1):
    	if int(G % i) == 0:
      
    여기서 int(G%i) == 0 인 것은 약수로 판정된다.
    위에서 설명한 대로 a+b가 2개의 약수중 큰 약수이기 때문에...
      
    약수에 맞는 a,b를 찾을 때 염두해야한다.
      
    2.약수에 맞게 a,b를 찾기
    여기서 나는 별도의 메소드로 분리 시켜두었는데, a,b가 헷갈리기 때문에 조금 바꾸면..
    def possible(c, d):
        for p in range(1, d):
            if c+p == d-p:
                return (c+p)
      
    해당 메소드를 호출하는 시점은 약수(i, int(G/i))가 구해지고 각각 넣게 된다.
    result = possible(i, int(G/i))
    위 메소드에서 c, d는 각각의 약수로.. 기존 연립 방정식은 다음과 같다.
    a+b = d
    a-b = c
      
    여기서 의문스러운 것은 c와 d의 위치가 바뀔 수 있지 않느냐 인데, 해당
    메소드가 1~G까지 약수 조합 모두(1, G) ~...~ (G, 1)을 체크하기 때문에
    순서 고려 없이 진행해도 된다. d가 무조건 큰수여야 한다는 조건이 맞지 않으면,
    답 역시 달라지기 때문.(수식 성립 안됨 -> 음수여야 풀리기 때문)
      
    우리가 구할 것은 가능한 a와 b 이다. a를 남기고 넘기면
    a = d-b
    a = c+b 이다. 
    이것이 if c+p == d-p: 에 해당하는 조건문이고, b로 가능한.. 범위
    (1~d)까지 b를 대입시켜서 구하면... p로 각각 비교한다.
    조건에 맞는 a와 b(p)가 있다면 해당 값을 리턴한다.
      
    3. 출력하기
    이렇게 리턴 된 값을 divisor에 추가 시키고, 값이 있는 경우 sorted 후 출력,
    없다면 -1 출력을 한다.
  

• 답안

    def possible(a, b):
        for p in range(1, b):
            if a+p == b-p:
                return (a+p)
      
    if __name__ == '__main__':
        G = int(input())
        divisor = []
        for i in range(1, G+1):
            if int(G % i) == 0:
                result = possible(i, int(G/i))
                if result != None:
                    divisor.append(result)
      
        for j in sorted(divisor):
            print(j)
      
        if len(divisor) == 0:
            print(-1)