[백준/Python3] 1024번. 수열의 합

문제

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

N과 L이 주어졌을 때, 길이가 L 이상이고, 모두 더해 N이 되는 연속된 수열을 구하는 문제다.

---

1. 첫 번째 풀이

사고 과정

몇 가지 떠올린 게 있었다. 1부터 L개 더해놓고, 오른쪽으로 한 칸씩 이동한다던지... (1 + 2 + 3이라면, 1을 빼고 4를 더해 2 + 3 + 4를 만드는 식)

아니면 N을 L로 나눈 후, 거기부터 왼쪽으로 움직여가며 찾는다던지... 등등.

 

그러다 문득 떠올린 게, 정답이 성립하는 특수한 조건이 있지 않을까? 하는 것이었다.

 

예를 들어, N = 18, L = 3라면 정답은 5 + 6 + 7이 된다.

이는 조금 돌려 생각해보면, 6 + 6 + 6을 만든 후, 맨 앞의 6에서 1을 빼, 맨 뒤의 6에 더한 것이다. 

 

L이 홀수일 때, L이 얼마가 되던, 결국 균등하게 나눈 후, 앞의 숫자에서 일정량을 빼 뒤에 더해주는 형태다. L이 5가 되어 4 + 5 + 6 + 7 + 8이 정답이라 해도, 이는 결국 6 + 6 + 6 + 6 + 6, 즉 6 * 5로 변형할 수 있다.

 

L이 짝수라면 어떨까? 6 + 6 + 6 + 6이라면, 5 + 6 + 6 + 7이 되어, 연속되지 않게 된다. 이를 연속된 수로 만들려면, 수열 뒤쪽의 절반에 1을 붙여야 한다. 즉, 원래 수열이 6 + 6 + 7 + 7이었다면, 이는 5 + 6 + 7 + 8로 만들 수 있다.

 

즉, 이를 정리하면

L이 홀수일 때: N % L == 0이면 수열이 존재한다.

L이 짝수일 때: (N - (L / 2)) % L == 0이면 수열이 존재한다. 혹은, N % L == L / 2라면 성립한다.

그 외의 경우는 수열이 존재하지 않는다. 또한, 수열이 존재한다면 그 정체도 손쉽게 파악할 수 있다.

 

예제 입력으로 판단해보자.

1. N = 18, L = 4: 18 % 4 == 2 == 4 / 2이므로 수열이 존재한다.
2. N = 18, L = 5: 18은 5, 7, 9, 11, 13, 15, 17 중 9로 나누어 떨어진다.
   이때 수열은 -2 -1 0 1 2 3 4 5 6이다.
   1. L이 짝수인 6, 8, 10, 12, 14, 16의 경우, 각각 나머지가 0, 2, 8, 6, 4, 2로, L이 12일 때 성립한다,
      이때 수열은 -4 -3 -2 -1 0 1 2 3 4 5 6 7이다.

문제 조건이 음이 아닌 정수 수열이기에, 9와 12는 조건에 맞지 않는다. 18은 아예 불가능하니 제외.

18을 거르는 건, 수열 18칸으로 18을 만들려면 모든 칸이 1이어야 하니 아예 불가능하기 때문. 조금만 더 생각해보면, L의 최댓값도 끌어낼 수 있을 것 같다.

 

수열의 특정 값이 음수가 되면 안 된다. 여기서 작아지는 건 앞쪽. 첫칸이 0이 되는 경우는 언제일까?

첫칸의 값을 구하는 방법은 N / L - L / 2다. 앞의 N / L은 같은 숫자로 모든 수열을 채우는(6 + 6 + 6) 행위고, 뒤의 L - 2는 가운데로부터의 거리, 즉 얼마나 뺏기느냐다. (L이 3이면 3 / 2 = 1, 맨 앞의 6이 1을 뺏겨 5가 된다.)

짝수라면(6 + 6 + 7 + 7, N = 26, L = 4), 4 / 2 = 2... 이렇게 계산하려니 1을 더 빼야 한다.

 

첫칸과 가운데칸의 거리는 홀수일 때는 2로 나누고 버림, 짝수일 때는 2로 나누고 1 빼기. 이를 묶어서 쓰려면 (L - 1) / 2가 될 것이다. (L이 3이면 2 / 2 = 1이되고, 4라면 3 / 2 = 1이 된다.)

그럼 첫번째 항을 구하는 공식은 N / L - (L - 1) / 2다.

 

이 (L - 1) / 2 (빼는 수)가 먼저 채워져 있던 값, 즉 N / L보다 크면 성립하지 않는다. 이후 L이 커진다면, N / L은 점점 줄어들고, (L - 1) / 2는 점점 커지니, 앞으로도 항상 조건을 만족하지 않는다. 수식을 한번 정리해보자.

 

N, L이 정해졌을 때 수열이 존재하는 경우는

(L - 1) / 2 <= N / L

L(L - 1) <= 2N (L은 2 이상, 100 이하의 자연수)

 

즉, 정리하면 아래와 같다.

 

수열 존재 판정법
L(L - 1) <= 2N이면, 수열의 존재 여부를 논할 수 있다.

L이 홀수일 경우, N % L == 0이면 수열이 존재한다. L이 짝수일 경우, N % L == L / 2면 수열이 존재한다.

 

수열 만들기

수열이 존재할 경우, 수열의 첫번째 항은 N / L - (L - 1) / 2다.

첫번째 항부터, L개의 연속된 자연수를 나열하면 수열이 된다.

 

예시로 확인

N = 18, L = 4

4 * 3 == 12 <= 18이므로 수열이 존재할 수 있다.

4는 짝수. 18 % 4 == 2 == 4 / 2이므로, 수열이 존재한다.

이때 첫째 항은 18 / 4 - 3 / 2 == 4 - 1 == 3이므로, 정답은 3 + 4 + 5 + 6이 된다.

 

이제 이걸 코드로 옮겨볼까?

코드

def get_first(sum, count):
    return sum // count - (count - 1) // 2

def make_numbers(first, count):
    result = ''
    for i in range(count - 1):
        result += str(first + i) + ' '
    result += str(first + count - 1)

    print(result)

# main
n, l = map(int, input().split())

while l * (l - 1) <= 2 * n:
    if l % 2 == 1:
        if n % l == 0:
            make_numbers(get_first(n, l), l)
            break
    else:
        if n % l == l // 2:
            make_numbers(get_first(n, l), l)
            break
    
    l += 1
else:
    print(-1)

 

파이썬은 main이 없어서 그런가, 조금 불편한 점이 있었다.

main 함수를 만들고 solve 함수로 감싸는 방식이 있다는데, while ~ else 문도 있다길래 오늘은 else 문을 써봤다.

결과

 

아쉽게도 틀렸습니다가 떴다. 내가 놓친 부분이 있을까?

---

2. 마지막 풀이

사고 과정

질문 게시판을 둘러보다, 반례를 하나 찾아냈다.

 

N = 1,000,000,000 L = 99일 때, 코드는 아래 결과를 출력한다.

 

7999938 7999939 7999940 7999941 7999942 7999943 7999944 7999945 7999946 7999947 7999948 7999949 7999950 7999951 7999952 7999953 7999954 7999955 7999956 7999957 7999958 7999959 7999960 7999961 7999962 7999963 7999964 7999965 7999966 7999967 7999968 7999969 7999970 7999971 7999972 7999973 7999974 7999975 7999976 7999977 7999978 7999979 7999980 7999981 7999982 7999983 7999984 7999985 7999986 7999987 7999988 7999989 7999990 7999991 7999992 7999993 7999994 7999995 7999996 7999997 7999998 7999999 8000000 8000001 8000002 8000003 8000004 8000005 8000006 8000007 8000008 8000009 8000010 8000011 8000012 8000013 8000014 8000015 8000016 8000017 8000018 8000019 8000020 8000021 8000022 8000023 8000024 8000025 8000026 8000027 8000028 8000029 8000030 8000031 8000032 8000033 8000034 8000035 8000036 8000037 8000038 8000039 8000040 8000041 8000042 8000043 8000044 8000045 8000046 8000047 8000048 8000049 8000050 8000051 8000052 8000053 8000054 8000055 8000056 8000057 8000058 8000059 8000060 8000061 8000062

 

하지만 이 수열의 길이는 125개로, 문제의 크기가 100이 넘어가면 -1이라는 조건에 부합하지 않는다.

 

쉽게 말해, while문 조건에 L 길이 제한을 빼먹었다. ㅎ....

코드

def get_first(sum, count):
    return sum // count - (count - 1) // 2

def make_numbers(first, count):
    result = ''
    for i in range(count - 1):
        result += str(first + i) + ' '
    result += str(first + count - 1)

    print(result)

# main
n, l = map(int, input().split())

while l * (l - 1) <= 2 * n and l <= 100:
    if l % 2 == 1:
        if n % l == 0:
            make_numbers(get_first(n, l), l)
            break
    else:
        if n % l == l // 2:
            make_numbers(get_first(n, l), l)
            break
    
    l += 1
else:
    print(-1)

 

결과

 

이렇게 정답을 맞췄다.

조금 더 고민해보고 반례를 찾아봤어야 했나? 싶기도 하지만, 시험장에서도 수열 개수가 100개가 넘었는지를 세진 않았을 것 같아서.... 다음부터 조건을 전부 지켰는지, 코드랑 확인해보는 시도를 해야겠다.

---

개선

사고 과정

이제 이 코드를 어떻게 개선할 수 있을지 고민해보자.

 

가장 먼저, make_numbers 함수를 손보려 했는데, Gemini가 좋은 방법을 하나 추천해줬다.

파이썬엔 range라는 함수가 있다고 (...)

 

이를 응용하면, string에 일일이 추가하는 대신 이렇게 코드를 만들 수 있다.

 

def make_numbers(first, count):
    numbers = range(first, first + count)
    result = ' '.join(map(str, numbers))

    print(result)

 

range로 수열을 생성하고, 이를 join으로 공백과 합친다. join은 문자열(String)에 내장된 함순데, 구분자 뒤에 붙여서 문자열을 만들 수 있다. 매개 변수 또한 문자열을 받는다. 리스트, 튜플, 세트 등 다양한 형식을 받을 수 있지만, 그 요소는 문자여야만 한다.

 

문자와 문자를 번갈아 입력해 하나의 문자열을 만들어준다. 구분자 공백(' ')과 문자 리스트 [3, 4, 5]를 받는다면, '3 4 5'라는 문자열을 만들어주는 함수다.

---

가장 효율적인 코드

내 코드와 비교

여러 코드를 둘러봤는데, 해 판정 방법이 사람마다 다양했다.

무언가 하나만 남기긴 애매했는데, 다른 분들은 홀/짝 여부와 무관하게 한번에 정수해를 판정한다는 점이 눈여겨볼만 했다.

---

강평

브루트포스하게 구현하기엔 꽤 막막했는데, 수학적으로 접근하니 꽤 쉽게 풀렸다. 이러니저러니해도 수학이 체질인건지...