[백준 2018번] 수들의 합 5 (파이썬/Python)

https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

모든 경우의 수에 대해서 해당하는 가짓수를 찾을 때마다 연산을 다시 한다면 상당히 비효율적일 것이다. 

따라서 이전에 했던 연산(합)을 그대로 이어나가는 방법을 이용하여 풀었다.

아이디어는 그리 복잡하진 않다.

 

 

맨 처음 합(total)을 1로 저장하고 start와 end로 구간을 정한다. 

그리고 start부터 end까지의 합을 total에 저장하는데

total < N 이면 end를 뒤로 하나 밀면서 total을 더해주고

total > N 이면 start를 end 쪽으로 당기고, 당긴 만큼 total에서 빼준다.

total == N 이면 count를 하나 올려주고, end를 뒤로 하나 밀어주며 total에 더한다. 위의 과정을 반복문 조건동안 반복하면서 최종 count를 출력하면 된다.합을 total로 저장하면 같은 연산을 두번이상 할 필요가 없기 때문에 효율적으로 문제를 해결할 수 있다.

 

N=15라면,

1 start end

2

3

4

5

6

7

8

9

10

 

total = 1

 

1 start

2 end

3

4

5

6

7

8

9

10

total = 3

 

1 start

2

3 end

4

5

6

7

8

9

10

 

total = 6

 

1 start

2

3

4 end

5

6

7

8

9

10

 

total = 10

 

1 start

2

3

4

5 end

6

7

8

9

10

 

total = 15

 

1 start

2

3

4

5

6 end

7

8

9

10

 

total = 21

 

이제 start가 땡겨져 오면서 연속된 수들의 합(total)이 15(N)이 되는 것을 찾음

1

2 start

3

4

5

6 end

7

8

9

10

 

 

start가 땡겨져 오다가 total이 15보다 작거나 같아지면 다시 end를 늘림.

(위와 같이 계속 반복)

코드로 보는 것이 이해가 더 쉬울 수도 있다.

 

import sys
input = sys.stdin.readline
N = int(input())
start = 1
end = 1
total = 1
count = 1  ## 자기 자신 포함

## 1, 2만 예외처리
if N == 1 or N == 2:
  print(1)
  sys.exit()

## 반복하며 카운트, end가 굳이 N까지 갈필요 없다고 생각해서 반복조건을 저런식으로 함.
while end < N//2 + 2:
  if total == N:
    count += 1
    end += 1
    total = total + end
  elif total < N:
    end += 1
    total = total + end
  else:
    total = total - start
    start += 1
print(count)

 

연필로 조금만 써봐도 알겠지만 굳이 end가 N까지 도달하지 않아도 N의 절반 정도에서 두 정수의 합이 N이되는 경우로 반복문이 마무리되는 것을 알 수 있어서 반복조건을 위의 코드와 같이 썼다.

(N의 범위가 10,000,000까지라서 조금이나마 시간을 줄이고자 굳이 끝까지 할 필요 없다고 생각했다.)

1과 2는 반복문의 조건을 end != N 으로 하지 않아서 생기는 예외로 따로 처리해주었다.

 

 

글에 대한 조언, 질문 모두 환영합니다.