백준 2018번 문제(수들의 합 5) 파이썬(Python) 풀이 [로밍맨]

문제 링크

www.acmicpc.net/problem/2018

2018번: 수들의 합 5

 

정답 코드는 아래와 같습니다.

def solve():
  n = int(input())
  cnt = 0
  for i in range(1, n+1):
    s = 0
    for j in range(i, n+1):
      s += j
      if s == n:
        cnt += 1
        break
      elif s > n:
        break
  print(cnt)
 
solve()
 

 

특별한 기법을 사용하지 않고, 모든 경우에 대해서 다 테스트 하여, 성립하는 경우에 cnt 를 증가시키는 형태로 구현하였습니다.

 

사실 이 문제는 위에 제출한 코드로 풀리는건 맞지만, 사실 저는 이렇게 하면 정답이 되지 않을 것으로 예상했습니다.

상기 코드의 복잡도를 계산하면 O(N^2) 인데, N이 10,000,000 이기 때문에 10억을 훨씬 넘기 때문입니다.

원래는 "이렇게 naiive 하게 풀이했더니 시간 초과가 발생했습니다" 라고 하려고 했는데,

"정답입니다" 라고 뜨는 바람에 촬영을 멈추어 버렸습니다.

 

728x90

 

기회가 된다면 아래 코드에 대해서도 영상을 제작해보겠습니다.

간단하게 힌트만 드리자면, r 은 나머지 q 는 몫을 의미합니다.

짝수와 홀수에 대해서 각각 다른 규칙이 성립하기에 첫 번째 for 문은 짝수에 대해서 계산하고, 두 번째 for 문은 홀수에 대해서 계산합니다.

규칙은 작은 수부터 직접 해보면서 발견하였습니다.

 

def solve():
  n = int(input())
  cnt = 0
  for i in range(2, n//2, 2):
    r = n % i
    q = n // i
    if r*2 == i and q - r > 0:
      cnt += 1
  for i in range(1, n//2, 2):
    r = n % i
    q = n // i
    if r == 0 and q - i//2 > 0:
      cnt += 1
  print(cnt)
 
solve()

 

 

풀이는 아래 영상을 참고 바랍니다.

www.youtube.com/watch?v=NgsMwd0UUYM

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)