https://www.acmicpc.net/problem/2018
모든 경우의 수에 대해서 해당하는 가짓수를 찾을 때마다 연산을 다시 한다면 상당히 비효율적일 것이다.
따라서 이전에 했던 연산(합)을 그대로 이어나가는 방법을 이용하여 풀었다.
아이디어는 그리 복잡하진 않다.
맨 처음 합(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 으로 하지 않아서 생기는 예외로 따로 처리해주었다.
글에 대한 조언, 질문 모두 환영합니다.
'📚알고리즘 > 백준' 카테고리의 다른 글
[백준 1253번] 좋다 (Python/파이썬) (0) | 2023.01.09 |
---|---|
[백준 1940번] 주몽 (Python / 파이썬) (0) | 2023.01.07 |
[백준 10986번] 나머지 합 (Python/파이썬) (0) | 2023.01.07 |
[백준 11660번] 구간 합 구하기5 (Python/파이썬) (1) | 2023.01.03 |
[백준 11659번] 구간 합 구하기4 (Python/파이썬) (2) | 2023.01.02 |