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 = T
www.acmicpc.net
3중 for문을 사용하면 쉽고 간편하게 구현할 수 있는 문제였다. 하지만 나는 3중 for문을 생각못하고 재귀호출로 구현해서 코드가 길어지고 복잡해진거 같다.
|
#include <iostream>
using namespace std;
int num;
bool eureka;
void Solution(int start, int sum, int pick)
{
if (pick == 3 && num == sum)
{
eureka = true;
return;
}
else if (pick >= 3 || sum > num) return;
int triNum;
for (int n = start; n < 50; n++)
{
triNum = (n * (n + 1)) / 2;
Solution(n + 1, sum + triNum, pick + 1);
Solution(n + 1, sum + (triNum * 2), pick + 2);
Solution(n + 1, sum + (triNum * 3), pick + 3);
}
}
int main(void)
{
int testcase;
cin >> testcase;
while (testcase--)
{
cin >> num;
eureka = false;
Solution(1,0,0);
cout << eureka << endl;
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 16day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 2503번: 숫자 야구 (c++) (0) | 2020.04.23 |
|---|---|
| 백준 15684번: 사다리 조작 (c++) (0) | 2020.04.22 |
| 백준 1748번: 수 이어 쓰기 1 (C++) (0) | 2020.04.20 |
| 백준 12100번: 2048(Easy) (C++) (0) | 2020.04.19 |
| 백준 15683번: 감시 (C++) (0) | 2020.04.18 |