[python] 백준 1292 - 쉽게 푸는 문제

출처 : 백준, https://www.acmicpc.net/problem/1292

1292번: 쉽게 푸는 문제

 

 

풀이

 

if __name__ == '__main__':
  a, b = map(int, input().split())

  num_arr = [i for i in range(1, 46) for _ in range(i)]
  
  print(sum(num_arr[a-1:b]))

 

이 풀이가 맞는지를 잘 모르겠는데 난 이렇게 풀었다.

먼저, 시작과 끝을 나타내는 입력 A, B가 1 ≤ A ≤ B ≤ 1000이므로 배열의 개수는 1000개 이상이 되어야한다.

길어봐야 쓸 데 없으니 길이가 1000개 이상이 되도록 하는 가장 최소의 수를 구해서 배열을 만들고,

그 배열을 잘라서 A부터 B까지 sum함수로 더한 값을 return하도록 하자.

 

1은 1번 2는 2번 나오니 1 + 2 + 3 + ...  + n ≥ 1000인 n을 구하면 된다.

이 식은 n(n+1)/2 ≥ 1000이고 1000은 10√10이므로 n은 10√20 근처에 있겠다.

10√20은 44.7....이므로 45라고 생각해 곱해보면 45 * 46 / 2 = 1035, 따라서 n은 45이다.

---

 

시간 복잡도

 

-

 

알게 된 점

 

파이썬에서 2중 for문을 한 줄로 적는 방법

 

위 풀이에서 [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ..., 45]의 배열을 만들기 위해 2중 for문을 사용하였다.

이를 원래 2중 for문으로 나타내면

 

for i in range(1, 46):
  for _ in range(i):
    num_arr.append(i)

 

이다. 이를 한 줄로 작성하면

 

num_arr = [i for i in range(1, 46) for _ in range(i)]

 

다음과 같은 코드가 된다. 순서는 아래와 같다.

 

 

고찰

 

-