문제
N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.
링크 참조
문제 풀이
L보다 같거나 긴 음이 아닌 정수 리스트를 만들면 된다.
단, 정수 리스트의 합은 N이 되어야 한다.
해당 리스트의 요소들을 오름차순으로 출력하면 된다.
나의 경우, 해당 요소들이 연속된 값이므로 첫 번째 값을 기준으로 L개를 합했을 때의
첫 요소를 구한 뒤 다음 값들을 알아내는 것을 아이디어로 하였다.
N이 18이고, L이 4라면 4개 이상의 연속된 숫자들로 18을 만들면 된다.
처음 수를 a로 가정하면 연속된 숫자들은 a+1, a+2, a+3이 된다.
따라서 4a+(0+1+2+3) = N 의 식으로 변경해 첫 번째 값 a을 구한다.
코드
N, L = map(int, input().split())
flag = 0
remain = 0
while L <= 100:
answer = []
remain = 0
flag = 1
for i in range(L):
remain += i
a = (N - remain) / L
if a>=0:
if a % 1 != 0:
L += 1
else:
for i in range(L):
answer.append(int(a)+i)
else:
break
Sum = sum(answer)
if Sum == N:
break
if (flag) and len(answer)>0:
answer.sort()
for i in answer:
print(i,end=' ')
else:
print(-1)
N, L로 입력 값을 저장받는다. flag은 while문을 들어갔는 지 확인하기 위한 flag이다.
위에서 말한 것처럼, remain이라는 변수에 L번 반복한다.
L개의 연속된 개수가 있다고 하면 0부터 L-1까지 합한 값이 a를 제외한 값들에 더해지는 값이다.
그 다음 N에서 해당 값을 빼고 L로 나누면 첫 번째 요소 a의 값이 나오게 된다.
만약 해당 값이 0을 포함한 정수라면 포함시키면 된다.
정수 % 1 == 0 을 이용하여 정수인지 확인할 수 있다.
만약 정수가 아니라면, L의 크기를 증가시킨다.
정수라면, 해당 a부터 a+1, a+2,, 로 L번만큼 answer 배열에 넣는다
Sum 변수로 answer의 모든 요소를 더한 다음, 해당 변수가 N과 같으면 while문을 탈출한다.
flag가 1이고, answer의 배열에 요소가 있다면, answer을 정렬하고 차례대로 출력한다.
while문에 들어간 적이 없거나, answer에 요소가 추가된 적이 없는 것은 수열이 없는 경우거나 L의 길이가 100보다 크다는 것이므로 -1을 출력한다.
💌
후기
너무너무 재미땅
