9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
/*
num = 1
MARK: => 1
num = 2
MARK: => 1
num = 3
MARK: => 1
num = 4
MARK: => 2, P(1) + P(2)
num = 5
MARK: => 2, P(2) + P(3)
num = 6
MARK: => 3, P(3) + P(4)
num = 7
MARK: => 4, P(4) + P(5)
num = 8
MARK: => 5, P(5) + P(6)
num = 9
MARK: => 7, P(6) + P(7)
num = 10
MARK: => 9, P(7) + P(8)
num = 11
MARK: => 12, P(8) + P(9)
num = 12
MARK: => 16, P(9) + P(10)
num = 13
MARK: => 21, P(10) + P(11)
num = 14
MARK: => 28, P(11) + P(12)
*/규칙을 찾는게 핵심인데 이게 너무 어렵다.. ㅜㅜ
#include <bits/stdc++.h>
using namespace std;
void pado9461(){
int testcase;
scanf("%d",&testcase);
for(int i=0;i< testcase;i++){
int n;
scanf("%d",&n);
long long dp[101] = {0};
dp[1] = 1;
dp[2] = 1;
dp[3] = 1;
for(int j=4; j<=n;j++)
dp[j] = dp[j-2] + dp[j-3];
printf("%lld\n",dp[n]);
}
}
'알고리즘 > DP' 카테고리의 다른 글
| [백준] 12015, 12738 가장 긴 증가하는 부분 수열 2,3 (0) | 2023.04.16 |
|---|---|
| [백준] 11055 가장 큰 증가하는 부분 수열 (0) | 2023.04.15 |
| [백준] 11053 가장 긴 증가하는 부분 수열 (0) | 2023.04.15 |
| [백준] 10844 쉬운 계단 수 (0) | 2023.04.13 |
| [백준] 1912 연속합 (0) | 2023.04.08 |