백준 10448 유레카 이론
문제
삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.
자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다.
Tn = 1 + 2 + 3 + ... + n = n(n+1)/2
1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,
4 = T1 + T2
5 = T1 + T1 + T2
6 = T2 + T2 or 6 = T3
10 = T1 + T2 + T3 or 10 = T4
이 결과는 증명을 기념하기 위해 그의 다이어리에 “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
풀이 과정
첫 번째 풀이는 그냥 3중 for
문을 이용해 단순하게 구했다.
입력으로 주어지는 수가 최대 1000
이라 삼각수를 45
번까지 구했다. 45번 삼각수
는 1035
이다.
첫 번째 for
문은 result
가 1
이거나 i번째 삼각수
가 K
보다 크거나 같으면 탈출한다.
두 번째 for
문은 result
가 1
이거나 i번째 삼각수와 j번째 삼각수의 합
이 K
보다 크거나 같으면 탈출한다.
세 번째 for
문은 i번째, j번째, k번째 삼각수의 합
이 K
와 같으면 result
의 값을 1
로 만들고 종료한다. 이외에 세 삼각수의 합
이 K
를 넘기면 탈출한다.
두 번째 풀이는 미리 1부터 1000의 자연수에 대해 삼각수를 구한다.
역시 3중 for
문을 이용해 세 삼각수의 합
이 1000
보다 작거나 같으면 삼각수의 합의 리스트의 원소를 1
로 만든다.
삼각수의 합의 리스트 eureka_nums
는 원소의 인덱스는 자연수를 의미한다.
원소의 값은 해당 인덱스의 값이 삼각수의 합으로 나타낼 수 있는지를 의미한다.
코드 1
test_case = int(input())
T = [(i * (i + 1)) // 2 for i in range(46)] # 삼각수의 최대 크기 n이 45일 때 1035
for _ in range(test_case):
K = int(input())
result = 0
for i in range(1, len(T)):
if result == 1 or T[i] >= K:
break
else:
for j in range(1, len(T)):
if result == 1 or T[i] + T[j] >= K:
break
elif result == 1:
break
else:
for k in range(1, len(T)):
if T[i] + T[j] + T[k] == K:
result = 1
break
elif T[i] + T[j] + T[k] > K:
break
print(result)
코드 2
T = [(i * (i + 1)) // 2 for i in range(46)] # 삼각수의 최대 크기 n이 45일 때 1035
eureka_nums = [0] * 1001
for i in range(1, len(T)):
for j in range(1, len(T)):
for k in range(1, len(T)):
tmp = T[i] + T[j] + T[k]
if tmp <= 1000:
eureka_nums[tmp] = 1
test_case = int(input())
for _ in range(test_case):
K = int(input())
result = eureka_nums[K]
print(result)
Author And Source
이 문제에 관하여(백준 10448 유레카 이론), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mynote/백준-10448-유레카-이론저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)