• Home
  • About
    • JOOS photo

      JOOS

      Joos's blog

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[백준] 2193번 : 이친수 with python3, cpp

03 Aug 2018

Reading time ~1 minute

방법 1

N = int(input())
D = [0] * (N + 1)

D[1] = 1

if N >= 2 :
    D[2] = 1
for i in range(3,N+1):
    D[i] = D[i-1] + D[i-2]
print(D[N])

문장 0 문장] 01
D의 n-1 D의 n-2
이 두가지 경우의 수만 더한다 생각하면 된다.
사실은 그것을 신경쓴 코드는 없지만…
경우의 수만 구하면 되서 이런 것이 가능한 것이다.

방법 2

n = int(input())
d = [[0, 0] for _ in range(n+1)]

d[1][0] = 0
d[1][1] = 1

if n == 1:
    print(1)
else:
    for i in range(2, n+1):
        d[i][0] = d[i-1][0] +  d[i-1][1]
        d[i][1] = d[i-1][0]
    print(d[n][0] + d[n][1])

D[N][L]에서 N은 글자의 길이 L은 마지막 수이다. 1이 연속되면 안됨으로 D[i][1]은 D[i-1][0]만 더한다. 0은 아무거나 됨으로 저렇 다 더한다(?)


#include <iostream>
using namespace std;
long long d[1001][2];
int main() {
    int n;
    cin >> n;
    d[1][0] = 0;
    d[1][1] = 1;

    for (int i=2; i<=n; i++) {
        d[i][0] = d[i-1][0] + d[i-1][1];
        d[i][1] = d[i-1][0];
    }
    long long ans = 0;
    for (int i=0; i<2; i++)
        ans  += d[n][i];

    cout << ans << '\n';
    return 0;
}



algorithm백준 Share Tweet +1