전체 방문자
오늘
어제
모달조아
Better than yesterday
모달조아
  • 분류 전체보기 (147)
    • PS (86)
      • BOJ (79)
      • 프로그래머스 (6)
    • 이론 (41)
      • 자료구조 (2)
      • 알고리즘 (8)
      • 데이터베이스 (1)
      • 운영체제 (1)
      • 네트워크 (3)
      • 디자인패턴 (7)
      • Java (13)
      • Spring (4)
      • JPA (1)
      • Git (1)
    • 개발 (18)
    • 프로젝트 (1)
    • 기록 (0)
      • 후기 (0)
    • etc (1)

최근 글

티스토리

hELLO · Designed By 정상우.
모달조아
PS/BOJ

BOJ 9461 파도반 수열

PS/BOJ

BOJ 9461 파도반 수열

2021. 7. 9. 01:17

boj 9461 파도반 수열

- 문제 링크

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

- 문제 해설

첫 5항만 제외하고 나머지 항들은 전부 규칙을 따라 증가하는 형태이다.
P(1)부터 P(10)을 보면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이다.
길이가 3인 삼각형은 1과 2를 더해서 생기고, 길이가 4인 삼각형은 1과 3을 더해서, 길이가 5인 삼각형은 1과 4를 더해서 생긴다.
D[i] = D[i-1] + D[i-5] 의 규칙을 따라 증가한다.
그러므로 1~5항을 따로 초기화해주고 나머지는 위 점화식을 따라 구해준다.

- 코드 보기

#include <iostream>
using namespace std;
int t;
int n;
long long P[105];
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
for (int i = 1; i <= 3; i++) P[i] = 1;
P[4] = 2;
P[5] = 2;
for (int i = 1; i <= t; i++)
{
cin >> n;
for (int j = 6; j <= n; j++)
{
P[j] = P[j - 1] + P[j - 5];
}
cout << P[n] << '\n';
}
}
저작자표시 (새창열림)

'PS > BOJ' 카테고리의 다른 글

BOJ 2011 암호코드  (0) 2021.07.12
BOJ 2225 합분해  (0) 2021.07.09
BOJ 2133 타일 채우기  (0) 2021.07.08
BOJ 1699 제곱수의 합  (0) 2021.07.08
BOJ 2579 계단 오르기  (0) 2021.07.08
  • boj 9461 파도반 수열
'PS/BOJ' 카테고리의 다른 글
  • BOJ 2011 암호코드
  • BOJ 2225 합분해
  • BOJ 2133 타일 채우기
  • BOJ 1699 제곱수의 합
모달조아
모달조아

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.