분류
수학(math), 두 포인터(two_pointer)
문제 설명
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.
예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.
N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.
입력
첫 줄에 정수 N이 주어진다.
15
출력
입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오
4
아이디어
-
연속된 자연수들의 합이 N인 경우를 찾는 것이므로 부분 연속 수열
-
투 포인터로 풀기
-
어차피 1~N까지의 자연수니까 포인터를 리스트의 인덱스로 둘 필요 없이, 숫자 자체로 지정하면 됨
코드1
N = int(input())
sum, cnt = 1, 1 # n 자체는 더할 필요 없이 n 이니까 cnt 1부터 시작
start, end = 1, 1 # 인덱스
while end != N: # 끝에 도달하기 전까지
if sum == N:
cnt += 1
# 새로운 해 찾기
end += 1
sum += end
elif sum > N: # 더한 값이 커지면
sum -= start
start += 1 # start 오른쪽 이동 == 왼쪽 거 빼는 효과
else: # 더한 값이 작아지면
end += 1 # end 오른쪽 이동 == 오른쪽 거 더하는 효과
sum += end
print(cnt)
- 부분 합이 n과 같을 때
end += 1은 다음 조합을 찾기 위한 코드 - 이게 좀 더 직관적인 듯(내 기준)
코드2
N = int(input())
end = 0
sum = 0
count = 0
for start in range(0, N):
while sum < N and end < N :
sum += end+1
end += 1
if sum == n:
count += 1
sum -= start+1
print(count)- 이코테 강의 기반 코드
- N보다 작을 때만 end를 1 증가, N보다 크거나 같다면 start를 1 증가
얻은 것
-
분명 투 포인터 내용도 열심히 보고 해결 아이디어도 손으로 따라가면서 공부한 다음에 딱 이틀 지나서 다시 푼 건데도 ...... 잘 안 풀리더라 ^,^ ....
-
잊지 않게 자주 복습하기
