STUDY/알고리즘
[백준] 유레카 이론 (Python)
seonyounggg
2021. 3. 1. 17:58
✏️ 문제
10448번: 유레카 이론
프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어
www.acmicpc.net
✏️ 풀이
수열 Tn은 Tn = n(n+1)/2의 공식을 갖는다.
이러한 수열 Tn을 저장하는 배열을 선언하여, 미리 삼각수 배열을 만들어 둔다.
이 때 중요한 것은, 시간 초과를 피하기 위해 배열의 크기를 적절하게 설정해야 한다.
문제에서 자연수 K가 1000 이하라고 명시되어 있으므로,
적절히 T45(= 45*46/2= 1035) 까지의 삼각수를 저장한다.
그 후, for문 돌면서 현재 자연수가, 삼각수 배열에서 3개를 선택하여 이를 합친 값과 같은지 판단한다.
중복선택이 가능하므로 Itertools.combination_with_replacement()를 사용하였다.
( 참고↓ )
[파이썬] itertools모듈
리스트 조합 관련된 알고리즘 문제를 풀다 보면 itertools 라이브러리가 풀이에 종종 등장한다. 사실 처음 봤을 땐 라이브러리 사용법을 암기해서 쓰는 것보다 직접 구현하는 게 차라리 빠르겠다
seonyounggg.tistory.com
✏️ 코드
import itertools
cnt = int(input())
triple = [n*(n+1)/2 for n in range(1, 45)]
for _ in range(cnt):
num = int(input())
for e in itertools.combinations_with_replacement([n for n in triple if n < num], 3):
if sum(e) == num:
print(1)
break
else:
print(0)
✏️ 생각
문제를 풀면서 실수했던 것 정리!
1. triple 배열에 0이 들어가도록 한 것
2. 3개의 삼각수는 중복 가능하나 이를 체크하지 못하고 단순 조합으로 푼 것