[BOJ2193 C++] 이친수

실버 3짜리 문제 ~

근데 학교에서 풀때는 진짜 생각 안났다..

처음에 recursive로 풀다가 푼줄알고 제출했는데 시 간 초 과

그래서 뭐지 하고

최대값 90 넣었는데 5분도 더 걸리길래 중간에 끊어버렸다.

집와서 샤워하고 다시 보니까 그냥 생각나더라 (근데 틀림)

왜틀렸냐면 .. int 형으로 값을 저장하게 했는데 ..

값이 커지니까 오버플로우나더라;; 그래서 틀렸다

값을 넣어볼 수 있는 입력이라면 최대 값도 넣어보자

long 형으로 선언하니까 제대로 나와서 채점하니 맞더라

어떻게 풀었냐!

간단히 생각하면 .. 이거 앞에서부터 읽는걸로 생각 안했다

뒤에서부터 계단을 밟았다. 그니까 맨 윗층에서 내려오는걸로 생각했다

계단이 그러니까 한층에 0이랑 1이 써있는 계단이 있는데,

그 계단을 밟을 수 있는 경우의 수를 체크체크하면 된다.

그리고 마지막에는 1이 써있는 계단으로만 들어가는 경우의 수를 체크!

왜냐면 항상 1로 시작해야한다고 했으니까 .. 1xxx 이런식으로 ..

한층에 0과 1이 써있는 계단 선언 하고 맨 마지막 칸은 우리가 넣어주자

long arr[91][2]; //최대 90칸

arr[N][0] = 1;
arr[N][1] = 1;

//마지막부터 내려올건데, 가장 위의 칸은 0과 1을 밟을 경우의 수는 각각 1개씩 이겠지

그다음에 더 생각해보면

다음 계단으로 내려갈 경우, 다음 계단의 0으로 들어갈 수 있는건 이전 계단의 0이라 써있는 칸과
1이라 써있는 칸 모두 가능하지

그런데 다음 계단에 1으로 들어갈 수 있는건 이전 계단의 0이라 써있는 칸 밖에 없잔하!

arr[N][0] = arr[N+1][0] + arr[N+1][1]; //0에서 내려가는 경우의 수 + 1에서 내려가는 경우의 수
arr[N][1] = arr[N+1][0]; //0에서 아래의 1이라 써있는 칸으로 내려가는 경우의 수만 !

점화식이라면 점화식이겠지..

이걸 이제 for문안에 샥 ~ 녹이면

//
// Created by 신성준 on 2023/03/05.

//거꾸로 생각하는 것이 중요 했음
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    long arr[91][2];

    for(int i = N; i >= 1; i--){
        if(i == N){
            arr[i][0] = 1;
            arr[i][1] = 1;
        }
        else {
            arr[i][0] = arr[i + 1][0] + arr[i + 1][1];
            arr[i][1] = arr[i + 1][0];
        }
    }
    cout << arr[1][1];

}

마지막에는 1이라 써있는 칸만 출력해주면 깔끔.