전체 방문자
오늘
어제
모달조아
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 정상우.
모달조아

Better than yesterday

PS/BOJ

BOJ 2193 이친수

2021. 6. 29. 05:03

boj 2193 이친수

쉬운 계단 수, 오르막 수와 비슷한 류의 문제이다. 길이가 N인 이친수의 경우의 수를 끝이 0이거나 1인 경우로 나눈다. 초기 값으로는 길이가 1일 때와 2일 때를 잡고, 그 값을 쌓아올려 길이가 N일 이친수의 갯수를 구한다. 길이가 3 이상인 이친수의 경우, 끝이 0인 경우 그 앞의 수로 0, 1이 올 수 있다. 끝이 1인 경우는 그 앞의 수로 0만 올 수 있다. 이를 바탕으로 테이블 D[i][j]를 길이가 i이고 맨 끝 수가 j인 이친수의 갯수로 정의하고 점화식을 설정했다.

j가 0일 때, D[i][j] = D[i-1][j] + D[i-1][j+1]
j가 1일 때, D[i][j] = D[i-1][j-1]

점화식을 바탕으로 코드를 구현했다.

#include <iostream>
using namespace std;

int n;
long long ans;
long long D[95][5];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    D[1][1] = 1;
    D[2][0] = 1;

    for (int i = 3; i <= n; i++)
    {
        for (int j = 0; j <= 1; j++)
        {
            if (j == 1) D[i][j] = D[i - 1][j - 1];
            else D[i][j] = D[i - 1][j] + D[i - 1][j + 1];
        }
    }

    ans = D[n][0] + D[n][1];

    cout << ans;
}
저작자표시 (새창열림)

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

BOJ 2156 포도주 시식  (0) 2021.07.01
BOJ 9465 스티커  (0) 2021.07.01
BOJ 11057 오르막 수  (0) 2021.06.29
BOJ 10844 쉬운 계단 수  (0) 2021.06.29
BOJ 9095 1, 2, 3 더하기  (0) 2021.06.28
    'PS/BOJ' 카테고리의 다른 글
    • BOJ 2156 포도주 시식
    • BOJ 9465 스티커
    • BOJ 11057 오르막 수
    • BOJ 10844 쉬운 계단 수
    모달조아
    모달조아

    티스토리툴바