[BOJ][실3][2193] 이친수

문제 링크

문제링크

첫 번째 풀이 : DP

알고리즘

가장 오른쪽 값은 1 또는 0입니다.

dp[i][0] : 길이가 i이고 끝자리가 0인 이친수의 갯수 dp[i][1] : 길이가 i이고 끝자리가 1인 이친수의 갯수

3자리 이상의 수에서, 끝자리가 0이라면 다음에 올 수 있는 수는 1 또는 0이고, 1이라면 0뿐입니다.

1. 2차원 dp 풀이
   • dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
   • dp[i][1] = dp[i - 1][0];
   • 출력 값 자료형 long long
2. 1차원 dp 풀이
   • n자리 이친수가 ??????라면, ?????0 또는 ?????1입니다.
   • ?????0의 경우 ?????가 무엇이든 상관없이 때문에 dp[n-1]
   • ?????1의 경우 반드시 ????01이어야 하기 때문에 ????는 무엇이든 상관없으므로 dp[n-2]
   • 따라서 dp[i] = dp[i-1] + dp[i-2]입니다.

정답코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 91;
const int MOD = 10007;
int arr[MAX][MAX];
ll dp[MAX][2];
bool visited[MAX][MAX];

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int n, m;

void show(void);
void bfs(int x, int y);

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  dp[1][0] = 0;
  dp[1][1] = 1;
  dp[2][0] = 1;
  dp[2][1] = 0;
  for (int i = 3; i <= n; i++) {
    dp[i][0] += dp[i - 1][0] + dp[i - 1][1];
    dp[i][1] += dp[i - 1][0];
  }
  cout << dp[n][0] + dp[n][1];


  return 0;
}

Success Notice: 수고하셨습니다.