[BOJ/백준] 2193 이친수

● [문제번호 2193] 이친수

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

2193번: 이친수

 

● 알아야 할 것

: 다이나믹 프로그래밍

: vector 자료구조와 메소드

 

● 풀이 과정

: 하나씩 Bottom - Up 과정으로 작성해보니 규칙이 보였다.

 

: 맨 앞자리에는 1이 오고

바로 그 다음자리에는 0이 와야만 한다.

 

그리고 그 다음자리부터는 index - 1 과 index - 2 의 방법의 갯수를 더한 것과 같다

5의 이친수가 만들어 지는 과정

1. 테이블 정의하기

→ 각 index 의 이친수 개수

 

2. 점화식 찾기

→ dp[index] = dp[index - 1] + dp[index - 2]

(피보나치 수열과 같은 방식)

 

3. 초기값 정하기

→ index가 1일 때 이친수 : 1 이므로 1개

→ index가 2일 때 이친수 : 10 이므로 1개

 

● 주의 할 것

: NULL

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// index자리 이친수의 개수
vector<long long> dp;
int N;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    dp.assign(N + 1, 0);
    
    // 초기값 설정
    dp[1] = 1;
    dp[2] = 1;
    
    // Bottom - Up
    for(int n = 3; n <= N; n++)
        dp[n] = dp[n - 1] + dp[n - 2];
    
    cout << dp[N];
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [400 - 다이나믹 프로그래밍 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1463	1로 만들기	https://pirateturtle.tistory.com/199
2	11726	2×n 타일링	https://pirateturtle.tistory.com/200
3	11727	2×n 타일링 2	https://pirateturtle.tistory.com/201
4	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/202
5	11052	카드 구매하기	https://pirateturtle.tistory.com/203
6	16194	카드 구매하기 2	https://pirateturtle.tistory.com/204
7	15990	1, 2, 3 더하기 5	https://pirateturtle.tistory.com/205
8	10844	쉬운 계단 수	https://pirateturtle.tistory.com/206
9	2193	이친수	https://pirateturtle.tistory.com/207
10	11053	가장 긴 증가하는 부분 수열	https://pirateturtle.tistory.com/208
11	14002	가장 긴 증가하는 부분 수열 4	https://pirateturtle.tistory.com/209
12	1912	연속합	https://pirateturtle.tistory.com/210
13	1699	제곱수의 합	https://pirateturtle.tistory.com/211
14	2225	합분해	https://pirateturtle.tistory.com/212