[Python] 백준 1024번 '수열의 합' 알고리즘

문제 

 

N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.

 

초기 idea

 

'수학적 관계식을 통한 프로그램 구현'

 

문제가 주어진 수열의 합을 구하는 것이 아니라, 합과 수열을 구성하는 수의 개수를 통해 수열을 출력하는 것이었다.

먼저, 수학문제를 풀듯이 수열의 합(N)과 수의 개수(L) 그리고 각 수의 수학적 관계를 알아보았다.

 

길이가 L로 고정된 경우, 어렵지 않게 수학적 관계를 알 수 있었고, 이를 프로그램화하는 것은 어렵지 않았다.

 

하지만 문제는 길이가 적어도 L인 가장 짧은 리스트, 즉, 길이가 L보다 클 수도 있다는 점이었다.

기존의 방법(수학적 관계를 통한 알고리즘 구현)을 살리면서, 이를 프로그램화 하는데 꽤 많은 시도가 필요했다.

 

다른 분들의 답안의 메모리와 코드 길이를 보니 내 코드는 비효율적인 것 같지만.. 배우는 입장에서 스스로 구현했음에 의미를 둔다ㅎㅎ

 

1) 길이가 L이고, 합이 N인 수열 출력

# 길이가 L로 고정된 문제에 대한 solution

# 입력부
N = int(input())
L = int(input())

# 문제의 제약 조건
if L >= 100:
    print('-1')

else:
    L_list = []              # init_a 값에 더하기 위해 1 ~ L-1의 수로 구성된 음이 아닌 정수 리스트 선언
    for i in range(1, L):
        L_list.append(L-i) 

    L_list.sort()

    sum_L_list = sum(L_list)

    init_a = (N - sum_L_list) / L  # 알고리즘의 핵심이 되는 수학적 관계식
    
    print(type(init_a))

    if init_a - int(init_a) == 0:

        solution_list = [int(init_a)]

        for i in range(0, len(L_list)):
            a = init_a + L_list[i]
            a = int(a)
            solution_list.append(a)

# 출력부
        for i in range(0, len(solution_list)):
            print(solution_list[i], end = ' ')

    else:
#        print('There is no solution!')
        print('-1')

 

2) 최소 길이가 L이고, 합이 N인 수열 출력

# 최소 길이가 L인 문제에 대한 solution

# 입력부
N, L = map(int, input().split())

# 문제의 제약조건
if L > 100 or L < 2 or N > 1000000000:
    print('-1')

else:
    
    L_list = []
    for i in range(0, 101):
        L_list.append(i)

    L_list.sort()

    sub_list = []
    for i in range(101):
        sub_list.append(sum(L_list[1:i+1]))
    
    init_a = (N - sub_list[L-1]) / L  # 초기 init_a는 길이가 L인 수열 문제와 동일하게 선언,
                                      # 아래 조건식들에 의해 변형됨
        
    if (init_a - int(init_a)) != 0:   # 길이가 L인 수열로 나타날 수 없음을 의미
        
        num = 0

        while (init_a - int(init_a)) != 0:    # 최소 길이를 위해 while문 활용
            
            num = num + 1
            
            if num > 98 or (L - 1 + num) > 100:
                break
            
            else:
                init_a = (N - sub_list[L - 1 + num]) / (L + num)
    
        if init_a >= 0 and (L + num) <= 100:   # 음의 정수, 오버 인덱스 방지를 위함
            solution_list = [] 

            for i in range(0, L + num):
                a = init_a + L_list[i]
                a = int(a)
                solution_list.append(a)
# 출력부
            for i in range(0, len(solution_list)):
                print(solution_list[i], end = ' ')
        
        else:
            print('-1')
            
    elif (init_a - int(init_a)) == 0 and init_a >= 0: # 길이가 L인 수열로 나타날 수 있음을 의미
        
        init_a = (N - sub_list[L-1]) / L 
    
        solution_list = []
    
        for i in range(0, L):
            a = init_a + L_list[i]
            a = int(a)
            solution_list.append(a)

# 출력부
        for i in range(0, len(solution_list)):
            print(solution_list[i], end = ' ')
            
    else:
        print('-1')

 

 

코드 활용 및 자세한 내용은 아래 github링크 참조를 바랍니다. 

감사합니다.

 

https://github.com/Hyung-code/BaekJoon

GitHub - Hyung-code/BaekJoon