[백준] 1292 쉽게 푸는 문제

브1

1. 문제

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

1292번: 쉽게 푸는 문제

 

2. 풀이

 

코테 준비하면서 구현 문제가 중요하다고 하길래 추천 문제를 풀고있다.

구현 문제들이 브론즈 문제들 추천이 많아서 일단 오랜만에 푸는데,

속도를 더 올려서 빠르게 마무리 할 수 있도록 해야겟다ㅜ___ㅜ

 

구간합을 구하는 문제인데,

 

## code ##

import sys
'''
- 시작 점, 끝점 구해서
    ~ 시작 숫자 같은 경우, 뒤에만 고려
    ~ 달라서 앞, 중간, 뒤로 나눠서 더하기
'''
start, end = map(int, sys.stdin.readline().split())

def square_sum(n):
    return n * n

def find_start(n): # 중간 총합 구하기
    return n * (n+1) / 2

start_num = [0, 0] # 시작, 남은 개수
end_num = [0, 0]

# start 숫자 찾기
tmp = 1
while True:
    sum = find_start(tmp)
    if sum >= start:
        start_num[0], start_num[1] = tmp, start - find_start(tmp-1)
        break
    tmp += 1

# end 숫자 찾기
tmp = start_num[0]
while True:
    sum = find_start(tmp)
    if sum >= end:
        end_num[0], end_num[1] = tmp, end - find_start(tmp-1)
        break
    tmp += 1

if start_num == end_num:
    total = end_num[0] * (end_num[1] - start_num[1] + 1)
else:
    total = (start_num[0] * (start_num[0] - start_num[1] + 1) + end_num[0] * end_num[1])
    for i in range(start_num[0]+1, end_num[0]):
        total += square_sum(i)

print(int(total))

 

살짝 풀이가 좀 긴것같기는 한데,,

 

1) 제곱합 함수 ==> 중간 숫자 최종에 더할때는 다들 제곱수라서 이 함수 사용
연속 숫자 합 함수 ==> 1, 2, 3, 4,,, 개씩 늘어서 어느 숫자가 시작인지 알 수 있고,

2) start, end의 수를 찾아주고, 이 숫자들이 몇 번째의 그 숫자인지 (3이면 첫번째 3인지 3번째 3인지) 찾아서

3) (1) 만약 start == end 숫자면, 그냥 몇번째인지 차이에 따라 곱해서 더해주고,
(2) 만약 start != end 숫자면, start 숫자 합 + (.end - start + 1) 숫자들의 제곱합 + end 숫자 합으로 분리해서 더해준다.

 

그렇습니다,, 좀 더 쉬운 방법이 있을거같긴한데ㅠ 일단 시간복잡도는 낮아서 만족 ㅎ,,,,ㅎ