🌟 유레카 이론
조건
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
1 초 | 256 MB | 14441 | 8402 | 6593 | 57.440% |
문제
삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.
자연수 n에 대해 n ≥ 1의 삼각수 Tn는 명백한 공식이 있다.
Tn = 1 + 2 + 3 + ... + n = n(n+1)/2
1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,
- 4 = T + T
- 1
- 2
- 5 = T + T + T
- 1
- 1
- 2
- 6 = T + T or 6 = T
- 2
- 2
- 3
- 10 = T + T + T or 10 = T
- 1
- 2
- 3
- 4
이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 궁금해졌다. 위의 예시에서, 5와 10은 정확히 3개의 삼각수의 합으로 표현될 수 있지만 4와 6은 그렇지 않다.
자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램을 만들어라. 단, 3개의 삼각수가 모두 달라야 할 필요는 없다.
입력
프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어있다.
출력
프로그램은 표준출력을 사용한다. 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력한다.
예제 입력 1
3
10
20
1000
예제 출력 1
1
0
1
풀이
def solution():
n = int(input())
tc = [int(input()) for _ in range(n)]
triangular = [int(i * (i + 1) / 2) for i in range(1, 45)]
for i in range(len(tc)):
eureka = 0
for j in range(len(triangular)):
for k in range(j, len(triangular)):
for l in range(k, len(triangular)):
if triangular[j]+triangular[k]+triangular[l] == tc[i]:
eureka = 1
print(eureka)
solution()
고민
하나하나 해볼 생각은 못했다. 되는 것만 찾아서 해볼 생각이었는데 방법을 못찾겠어서 하나하나 다 해보았다.
'백준 알고리즘' 카테고리의 다른 글
[BOJ] 백준_9094번_수학적 호기심_Python3 (0) | 2023.12.03 |
---|---|
[BOJ] 백준_13305번_주유소_Python3 (0) | 2023.12.02 |
[BOJ] 백준_1789번_수들의 합_Python3 (0) | 2023.11.30 |
[BOJ] 백준_10817번_세 수_Python3 (0) | 2023.11.29 |
[BOJ] 백준_2751번_수 정렬하기 2_Python3 (3) | 2023.11.28 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!