반응형
<코드>
#include<iostream>
#include<stdio.h>
using namespace std;
long long DP[101];
int T, N;
int main()
{
cin >> T;
while (T--)
{
cin >> N;
DP[1] = 1;
DP[2] = 1;
DP[3] = 1;
for (int i = 4; i <= N; i++)
{
DP[i] = DP[i - 2] + DP[i - 3];
}
cout << DP[N] << "\n";
}
return 0;
}
점화식은 A[N] = A[N-2] + A[N-3] 인 것을 쉽게 찾을 수 있다. 그리고 N값이 79 이상일 경우 DP값이 int형의 범위를 넘어가버려서 왜 틀렸을까? 하면서 많이 헤맸다. DP의 자료형을 long long형으로 바꿔주면 정상 출력된다.
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 �
www.acmicpc.net
반응형
'🧩PS > 🥈Nomal' 카테고리의 다른 글
| [C/C++] 백준 1932번 - 정수 삼각형(DP) (0) | 2020.11.22 |
|---|---|
| [C/C++] 백준 1149번 - RGB거리(DP) (0) | 2020.11.01 |
| [C/C++] 백준 1904번 - 01타일 (DP) (0) | 2020.10.19 |
| [C/C++] 백준 14889번 - 스타트와 링크 (DFS, 백트래킹, 비트마스킹, 브루트포스) (2) | 2020.10.14 |
| [C/C++] 백준 14888번 - 연산자 끼워넣기 (DFS, 백트래킹) (0) | 2020.10.07 |