[Python] 1024번 수열의 합

1024번: 수열의 합 (acmicpc.net)

1024번: 수열의 합

---

 

22/08/31

 

예전에 북마크 해두었던 문제인데 풀은 문제이다.

 

실버 2 치고는 수학적 발상이 조금 필요한 것 같아 실버 1로 기여했다.

 

---

 

문제 접근 방법:

 

 

N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 것이 문제에서 주어진 정보이다.

 

찾을 수 없다면 -1을 출력하면 된다.

 

정말 간단하고 짧다.

 

먼저 나는 길이가 적어도 L이 된다고 했기 때문에, 길이가 L보다 클 수도 있다는 사실에 주목했다.

 

그러면 처음에는 길이를 L로 정해놓고 리스트의 범위를 오른쪽으로 옮겨가며 탐색을 진행하다가 못 찾으면 L을 하나 크게 만들고, 찾고...

그렇게 반복을 하다가 찾는다면 멈추고, 만약 찾지 못하고 일정 기준을 넘으면 -1을 출력하기로 했다.

 

그러면 먼저 그 일정 기준을 세우기로 했다.

 

우리는 길이를 늘려가며 탐색을 진행한다고 했다.

 

근데 어느 순간이 되면 리스트의 길이가 너무 길어져서 합을 구하면 N을 그냥 넘어갈 때가 있을 것이다.

 

그 리스트의 합을 가장 최소로 하는 경우가 0부터 시작하는 경우인데, 만약 그 경우임에도 그냥 합을 구해서 N을 넘는다면, 그건 그냥 리스트의 길이가 너무 길어진 것이라고 보아도 된다.

 

이해가 잘 안갈 수도 있으니, 문제에 나와있는 예시로 이해를 해보자.

 

N = 18이고, L = 5이다.

 

우리는 합이 18이 되는 길이가 5 이상의 연속된 정수 리스트를 찾고 싶다.

 

근데 길이가 5이상의 연속된 정수 리스트 중에서 제일 합이 작은 것은 [0, 1, 2, 3, 4]인데, 이 리스트의 합을 구하면 10이다.

합이 N보다 작기 때문에 오른쪽으로 옮겨서 [1, 2, 3, 4, 5]의 합을 구해본다. 15가 나왔다.

합이 N보다 작기 때문에 오른쪽으로 옮겨서 [2, 3, 4, 5, 6]의 합을 구해본다. 20이 나왔다.

 

합이 N보다 커졌기 때문에 길이를 1 늘려서 이제 길이가 6인 연속된 정수 리스트 중에서 찾아보자.

[0, 1, 2, 3, 4, 5]의 합은 15다. 합이 N보다 작기 때문에 오른쪽으로 옮긴다.

[1, 2, 3, 4, 5, 6]의 합은 21이다.

 

합이 N보다 커졌기 때문에 길이를 1 늘려서 이제 길이가 7인 연속된 정수 리스트 중에서 찾아보자.

[0, 1, 2, 3, 4, 5, 6]의 합은 21이다.

이렇게 제일 합이 작은 리스트로 골랐음에도 불구하고 리스트의 길이가 너무 길어서 N을 그냥 넘어버리기 때문에 이 경우 종료를 해준다.

 

이런 식으로 찾으면 금방 찾을 수 있을 것이라고 생각했다.

 

근데 곰곰히 한번 더 생각해보니, 리스트의 길이가 너무 길어질 때, 그걸 판단하기 위한 용도로만 저 아이디어를 사용해야겠다는 생각이 들었다.

 

오른쪽으로 옮겨서 계속 구하는 발상은 조금 시간 면에서나 많이 불리할 것이라고 생각했다.

 

때문에 만약 합이 N이 되고 길이가 L이상인 연속된 리스트가 존재한다면 - 그 리스트의 중간 값만 잘 구한다면, 우리는 리스트의 길이를 알고 있고, 연속된다는 사실을 알고 있어서 쉽게 그 리스트를 구할 수 있을 것 같다는 생각이 들었다.

 

그렇다면 "리스트의 중간 값은 어떻게 구할 것이냐?"가 문제인데, 문득 "가우스는 등차수열의 합 공식을 '가운데를 기준으로 하여 끝 값들을 더한다'는 아이디어로부터 만들었다"라는 사실을 떠올렸다.

 

그렇다면, 예를 들어서 길이가 3이고, 더했을 때 15가 되는 리스트라면 [4, 5, 6]이 될 것이다.

 

근데 이 중간값 5는 15 // 3으로 부터 나왔다는 사실을 알 수 있다.

 

이러한 예시를 하나 생각하니, N // L 주변에서 찾으면 될 것 같다는 생각이 들었다.(주변이라고 말한 이유는, 길이가 짝수인 리스트의 경우 중간값이 모호하고, 나누기를 했을 때 소수점이 나올 수도 있기 때문에)

 

N // L은 어디까지나 몫을 취한 나눗셈이기 때문에 주변이라고 하면 ±1 정도의 오차를 가지고 있을 것이라고 생각했다.

 

또한 N // L은 중간 값이기 때문에 리스트가 시작하는 숫자를 L을 통해 찾아야 하는데, 이 경우 L // 2를 중간 값에 빼서 구하면 될 것이라고 생각했다.

 

이때, 리스트가 시작하는 숫자는 항상 0보다 커야 하기 때문에 max함수를 취해줌으로써 음수를 방지해주었다.

 

이렇게 대충 생각하고 구현을 해보았더니 잘 작동이 되서 다행이라고 생각했다.

 

실버 치고는 어려웠던 문제였다.

 

---

아래는 위의 아이디어를 토대로 작성한 코드이다. 더보기를 누르면 확인할 수 있다.

# 1024번 수열의 합
# 수학
N, L = map(int, input().split())
while L*(L-1)//2 <= N and L <= 100:
    k = N // L
    if sum(range(max(0, k - L//2), k - L//2+L)) == N:
        print(*range(max(0, k - L//2), k - L//2+L))
        break
    if sum(range(max(0, k - L//2 + 1), k - L//2 + 1+L)) == N:
        print(*range(max(0, k - L//2 + 1), k - L//2 + 1+L))
        break
    if sum(range(max(0, k - L//2 - 1), k - L//2 - 1+L)) == N:
        print(*range(max(0, k - L//2 - 1), k - L//2 - 1+L))
        break
    L += 1
else:
    print(-1)