-
1024. [Python]수열의 합Python_알고리즘/Silver II 2023. 8. 4. 11:02
1. 문제
https://www.acmicpc.net/problem/1024
1024번: 수열의 합
첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 수학
3. 파이썬 코드
N, L = map(int,input().split()) # 수학적 귀납법 # N = (x+1) + (x+2) + ... (x+L) => Lx + (L(L+1)/2) # 리스트 길이가 L ~ 100 까지 증가 for i in range(L,101): # N 의 값을 구하기 위해서는 x 개만큼 L이 있고 나머지 1~L까지 합은 L*(L+1)/2 로 나타낼 수 있다. x = N - ((i * (i+1))/2) # 이렇게 식에 맞게 코드를 작성하여 변수에 할당하면 x 값을 구할 수 있고 # 만약 x 값이 i 로 나누어 떨어진다면 if x % i == 0: # k 값이 x를 i로 나눈 몫에 +1 을해준다 k = x//i + 1 # 이 k 값이 음수가 아닐 경우 k ~ (k+i-1) 까지 출력한다. if k >= 0: for j in range(i): print(int(k+j),end=" ") # 조건이 끝나면 break 를 걸어서 더이상 찾지 않도록 한다. break # 만약 끝까지 탐색했는데 값이 없는경우 -1 출력 else: print(-1)
4. 문제를 풀고난 후 생각
- 수학적 개념이 부족해서 스스로 풀지 못했던 문제였다.
- 임의의 수 x에 대해서 x~x+L 까지 합을 구하면 N 이 되는 식을 접해본 적이 없어서 검색을 통해서 알아냈고, L을 설정하는 기준이 리스트 길이가 100까지 제한을 뒀으며 리스트 길이에 따라 조건에 맞는 값들의 리스트가 있는 경우 출력하고 break를 해줬다.
- 조건에 맞지 않으면 else 구문을 통해서 -1을 출력하게 된다.
- 수학적 접근을 할줄 모르면 아예 손을 댈 수 없는 문제였다.
5. 문제를 푸는데 도움이 되는 지식
- 수학
'Python_알고리즘 > Silver II' 카테고리의 다른 글
1260. [Python]DFS와 BFS (0) 2023.08.08 1874. [Python]스택 수열 (0) 2023.08.07 1541. [Python]잃어버린 괄호 (0) 2023.08.06 1254. [Python]팰린드롬 만들기 (0) 2023.08.04 10799. [Python]쇠막대기 (0) 2023.02.13