백준 9461 파도반 수열 (C++)

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

9461번: 파도반 수열

 

문제!

---

 

 

위 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

 

---

삼각형을 계속 붙여나가면서 길이가 가장긴변을 체크!

그 변의 길이 만큼의 정삼각형을 다시붙여 점점 도형을 늘려나가면서 만들어지는

N 번째 정삼각형의 한변의 길이를 출력하는 문제

 

이 문제는 그림을 보면 쉽게 이해 할 수 있습니다.

 

삼각형의 생성 순서를 생각해보면

1~5까지는 규칙없이 생성되는데

 

6번째 부터는 

6 >> 5번삼각형 + 1번삼각형

7 >> 6번삼각형 + 2번삼각형

8 >> 7번삼각형 + 3번삼각형

9 >> 8번삼각형 + 4번삼각형

10 >> 9번삼각형 + 5번삼각형

 

계속 이런식으로 반복 됩니다.

이런식으로 dp에 저장해주고 저장한 값을 불러오면 끝!

 

 

코드는 아래와 같습니다.

 

#include <iostream>
#pragma warning(disable:4996)
using namespace std;

// 1 1 1 2 2 3 4 5 7 9

long long dp[101]={0};

void cal() {
    dp[1] = 1, dp[2] = 1, dp[3] = 1, dp[4] = 2, dp[5] = 2;

    for (int i = 6; i < 101; i++) {
        dp[i] = dp[i - 1] + dp[i - 5];

    }
}

int main() {
    int n;
    int num;
    cal();
    scanf("%d", &n);
    
    while (n--) {
        scanf("%d", &num);
        cout << dp[num] << endl;
    }
}

 

 

 

 

  

 

 

 

 

 

!

 

 

 

 

틀린점이 있다면 댓 달아주세요!