Algorithm/Baekjoon

[Algorithm] Baekjoon 9461번 : 파도반 수열

MaxLevel 2022. 11. 29. 20:31

https://www.acmicpc.net/problem/9461

 

9461번: 파도반 수열

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
vector<int> results;
long long p[101] = { 0 };
int maxNum = 6;
 
 
void solve(int n)
{
    int result = 0;
 
    if (n > maxNum)
    {
        for (int i = maxNum+1; i <= n; i++)
        {
            p[i] = p[i - 1] + p[i - 5];
        }
 
        maxNum = n;
    }
    
    cout << p[n] << endl;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 2;
    int input = 0;
 
    p[0] = 0;
    p[1] = 1;
    p[2] = 1;
    p[3] = 1;
    p[4] = 2;
    p[5] = 2;
    p[6] = 3;
 
    cin >> t;
 
    for (int i = 0; i < t; i++)
    {
        cin >> input;
        solve(input);
    }
}
 cs

 

규칙은 빨리 찾았는데, 배열 데이터타입을 크게 안잡아놔서 헤맨 문제다.

그림보면 i번째의 새로운 삼각형의 변의 길이는, i-1번째와 i-5번째 삼각형변의 길이를 더한것과 일치하단걸 알 수 있다.

나는 바보같이 배열을 int로 너무 작게 잡아놨어서.. 

어쨌든 규칙찾는건 어렵지 않다.