https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
문제 해결을 위한 과정
문제에서 주어진 10개의 숫자를 통해 규칙을 찾을 수 있었던 문제였습니다. 표로 정리하면 다음과 같습니다.
| p(1) | p(2) | p(3) | p(4) | p(5) | p(6) | p(7) | p(8) | p(9) | p(10) |
| 1 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 7 | 9 |
p(10)이후로 삼각형을 더 그려서도 파악할 수 있지만 규칙은 p(i) = p(i-1)+p(i-5) 인것을 알 수 있다. 따라서 다음의 규칙을 소스코드로 작성하면 다음과 같다.
소스코드 - python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
tc = int(input())
for i in range(tc):
n = int(input())
dp = [0] * (101)
dp[0] = 1
dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 2
for i in range(5, n+1):
dp[i] = dp[i-1] + dp[i-5]
print(dp[n-1])
|
cs |
소스코드 - c++
|
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
|
#include <bits/stdc++.h>
#define MAX 101
using namespace std;
int main(void) {
int tc;
scanf("%d",&tc);
for(int i = 0; i < tc; i++) {
int n;
scanf("%d", &n);
long long dp[MAX] = {0, };
dp[0] = 1;
dp[1] = 1;
dp[2] = 1;
dp[3] = 2;
dp[4] = 2;
for(int j = 5; j < n+1; j++) {
dp[j] = dp[j-1] + dp[j-5];
}
printf("%lld\n", dp[n-1]);
}
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 숨바꼭질 1697번: 숨바꼭질(Python, cpp) (0) | 2022.02.04 |
|---|---|
| 백준 알고리즘 11052번: 카드 구매하기(Python) (0) | 2022.02.02 |
| 백준 알고리즘 2193번: 이친수(Python) (0) | 2022.01.31 |
| 백준 알고리즘 11057번: 오르막 수(Python) (0) | 2022.01.29 |
| 백준 알고리즘 9251번: LCS(Python) (0) | 2022.01.29 |