💻 Computer Science/Algorithm🐇

[python] 백준 1024 : 수열의 합

노가다 권씨 2024. 2. 20. 23:08
728x90
반응형

(정답코드는 제일 밑에 있읍니다. )

 

입력값은 target number n과 length l입니다. target number을 최소 l개의 연속한 자연수의 합으로 나타내야하는 문제인데요, 만약 length가 100이 넘어가거나 해당 리스트가 존재하지 않는다면 -1을 출력합니다.

예를들어 입력값이 (n:15, l:3)이라면 답은 더했을때 15가되는 3개이상의 연속한 자연수 4,5,6이 되겠지요.

 

코드를 짜기전 논리구조를 생각해봅시다. 

논리구조 설명할땐 그림이 최곤데 ㅋㅋ 주저리주저리 글을 썼네요 그냥 수학계산입니다.

코드로 구현해봅시다.

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

while True:

    sum_plus = l*(l-1)*(1/2)

    if (n-sum_plus)%l==0 and ((n-sum_plus)//l)>=0:

        for i in range(l):

            print(int(((n-sum_plus)//l)+i),end=' ')
            
        break

    elif (n-sum_plus)%l!=0 and (n-sum_plus)>=l:
        l+=1
        
    elif (n-sum_plus)%l!=0 and (n-sum_plus)<l:

        print('-1')
        break
        
    elif l>100:
        print('-1')
        
        break

나머지 숫자의 합인 sum_plus를 정의해주고 n-sum_plus인 k*l이 l로 나눴을때 나머지가 0인지 (자연수 k가 존재하는지) , 그 k는 0이상인지를 첫번째 if문에서 판단해줍시다. 만약 모든 조건을 통과한다면 (자연수 k가 존재한다면) k부터 k+(l-1)까지 for문으로 출력해줍시다. 이때 한줄에 모두 출력해야하므로 print문에 end=' '을 넣어 줄바꿈하지않고 공백으로 나눠 출력합시다. 바로 아래 elif조건은 자연수 k가 존재하지않고, n=sum_plus가 l보다 크거나 같은상황입니다. 정확히 입력받은 l개만큼의 자연수의 합으로는 안나타나진다는 뜻입니다. 이땐 l에 1을더해 다시 검사해봅시다. 그 밑 elif조건은 자연수 k가 존재하지 않는데 n-sum_plus가 l보다 작은경우입니다. 즉, k*l<l인 경우로 더이상 조사가 불가능한 상황입니다. 이땐 -1을 출력해줍니다. 밑에는 리스트 길이가 100초과인 경우로 이때도 -1을 출력합니다. while문의 종료조건이 명시되어있지 않으므로 print로 출력후 break를 사용해 루프를 빠져나가야합니다.

 

근데 이대로 제출하면 1%에서 바로 틀려버립니다. 테스트케이스를 여럿 생각해봅시다. 

일반적인 상황 / 혹시 리스트에 음수가 포함되는가? (ex. n=0 ,l=3일때 -1대신 -1,0,1출력되는가?) / 리스트 길이가 100이 넘어갈때도 출력이되는가? 등등 여럿 테스트케이스를 만들어 입력해본결과... 이전에 풀었던 문제에서 범한 실수와 비슷한 결의 실수를 해버렸습니다.. 바로 이 코드에 리스트 길이가 100이상인 경우를 입력해도 그대로 출력된다.. 는 치명적인 테스트케이스를 발견했습니다.. 이유는.. 제일 위 if문에 리스트 길이에 대한 조건이 없기때문에, 나머지 조건을 충족시킨다면 리스트길이가 100이 넘어도 제일 첫 if문에 걸려서 그대로 출력이 되는것입니다....

 

if문을 작성할때 어디까지 걸리는지 생각을 대충했네요.. 처음 if문에 리스트 길이에 대한 조건도 추가합시다. 그런데..

쭉쭉 올라가다 77%에서 이제는 시간초과가 발생하고맙니다. 

 

제한시간이 2초이므로, 직접 시간을 측정해봅시다. 

import time
t_start = time.perf_counter()
##시행시간을 측정하고자하는 코드
t_end = time.perf_counter()
print(t_end-t_start)

위는 알고리즘의 소요시간을 '직접'측정하는 방식입니다. time모듈을 이용해 코드 시작전 시간, 종료 후 시간의 차이를 계산해 출력합니다. 이 방법은 간편하지만 컴퓨터 메모리 사용량에 따라 측정시간이 달라질수있다는 단점이 있습니다.

일단 돌려봅시다. 시작시간은 코드 제일 윗부분이 아닌, 입력값을 받은 직후부터 측정합니다.

 

아... 참고로 각 출력별 가장 마지막에 있는 수치가 시간(초)입니다. -1을 출력하는 케이스는 소요시간이 약 0.008~9초로 짧지만 .. 리스트 길이가 길수록 소요시간이 늘어납니다. 13.4초까지 기록하면서 제한시간을 훌쩍넘어버리네요

while문과 for문을 중첩해서 쓴게 문제일까요? 근데 위 코드에서 for문은 단순 출력을 위한 for문인데.. while문을 없애고 

위 시간초과한 테스트 케이스를 다시 입력해봅시다

 

import time

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

t_start = time.perf_counter()

sum_plus=l*(l-1)*(1/2)

if (n-sum_plus)%l==0 and ((n-sum_plus)//l)>=0 and l<=100:

    for i in range(l):
        print(int(((n-sum_plus)//l)+i),end=' ')

elif (n-sum_plus)%l!=0 and (n-sum_plus)<l:
    print('-1')

elif (n-sum_plus)%l!=0 and (n-sum_plus)>=l:
    contin_sum(l+1)

t_end = time.perf_counter()

print(t_end-t_start)

출력용 for문이 과연 시간초과에 영향을 주는지 실험해봅시다. 테스트 케이스는 n=999,999,999 l=81로 입력해봅시다

 

시간이 더 증가했네요 15초..? 사실 컴퓨터의 컨디션 이슈도 있겠지만 어쨌든 for문을 좀 고쳐봅시다.

힌트를 얻은부분은 문제에있었습니다. 문제는 '리스트'라고 말하고있죠. 그러면 for문안에서 바로 출력하지않고 리스트를 만들어 리스트에 넣는동작만 한뒤 while문 밖으로 빼서 리스트의 element를 출력하면 어떨까요?

 

n,l = map(int,input().split())
list_ans=[]

while True:

    sum_plus = l*(l-1)*(1/2)

    if (n-sum_plus)%l==0 and ((n-sum_plus)//l)>=0 and l<=100:

        for i in range(l):

            list_ans.append(int(((n-sum_plus)//l)+i))
            
        break

    elif (n-sum_plus)%l!=0 and (n-sum_plus)>=l:
        l+=1
        
    elif (n-sum_plus)%l!=0 and (n-sum_plus)<l:

        list_ans.append(-1)
        break
        
    elif l>100 or (n-sum_plus)<0:
        list_ans.append(-1)
        
        break

for i in range(len(list_ans)):
    print(list_ans[i],end=' ')

이런식으로.. 사실 크게 달라진게 없지않나..? 싶지만 띠용? 맞았습니다!!

왜..그러죠? 빅오의 관점에선 시간복잡도가 달라지지 않지않나..? 어차피 for문안에서 계산하는건 똑같은데 다만 print와 append 동작의 차이일뿐인데..

직접 시간을 측정한결과 13.36초로 이전기록과 차이가 있으려나..? 일단 제한시간이 2초인데도 통과를 한거보면 시간 측정은 저의 똥컴이슈인거같네요. 

이건 차후에 시간복잡도에 대해 더 알아보고 계속 업데이트하겠읍니다

솔직히 리스트로 바꾸고 제출할때 안될줄알았는데 갑자기 정답처리되서 기분은 좋지만 찝찝... 원인을 제대로 모른채로 맞아버렸으니 이 점은 계속 짚고넘어가야할듯합니다.

반응형