BOJ_1292 쉽게 푸는 문제

• TOC {:toc}

이 글은 백준 온라인 저지의 1292번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.04.13

A, B = map(int, input().split())

N = [int((1 + (8 * i - 7) ** 0.5) / 2) for i in range(A, B + 1)]
print(sum(N))

아이디어 & 풀이

순서와 수열을 나열해보면 다음과 같다.

i | 1 2 3 4 5 6 7 8 9 10 ...
n | 1 2 2 3 3 3 4 4 4 4  ...

숫자가 증가하는 지점만 골라서 보면 i와 n은 다음과 같은 관계를 갖는다.

i | 1 3 5 7 ...
n | 1 2 3 4 ...

$$ i = {n(n+1) \over 2} + 1 = {n^2+n \over 2} + 1\ n^2+n+2-2i = 0 \ n = {-1 + \sqrt{(8i - 7)} \over 2} $$

숫자가 증가하는 지점보다 외의 i의 경우 계산 결과는 n.xxx 이기 때문에 소수점 아래를 버려주면 n이 된다.

• 즉, 구한 값에 int를 취해주면 위 식은 모든 수열에 대해 성립한다.

# i번째 수에 해당하는 n
int((1 + (8 * i - 7) ** 0.5) / 2) 

이를 이용해 주어진 두 수의 범위에 해당하는 n으로 이루어진 리스트를 만들어 그 원소의 합을 출력한다.

참고 답안

# 풀이 1-1
num = []
# 원소의 개수는 n까지 입력했을 때 n(n+1)/2개이다.
# 45 * 46 / 2 = 1035로 처음 1000개를 넘는 수이다.
for i in range(1, 46):
    # 기존의 배열에 현재 i값을 갖는 배열 i개를 만들어서 더한다.
    num += [i] * i
    
A, B = map(int, input().split())
# 인덱스는 0부터 시작하므로 A 번째 수는 인덱스 A-1에 위치한다.
# A 번째부터 B 번째 까지 리스트를 추려서 그 원소를 더한 값을 출력
print(sum(num[A - 1:B]))

# 풀이 1-2
A, B = map(int, input().split())
l = [1]

# 위처럼 배열을 미리 생성하되 e번째까지만 생성한다.
while len(l) < B:
    # 현재 배열의 마지막 원소보다 1 증가한 원소를 갖는 배열을 그 값의 개수만큼 추가한다.
    l.extend([l[-1] + 1] * (l[-1] + 1))

print(sum(l[A - 1:B]))

아이디어 & 풀이

많은 경우 위 수열을 1000번째 원소까지 (입력값이 1과 1000 사이이기 때문에) 리스트 안에 전부 만들고 주어진 범위를 출력하는 방식을 사용했다.