동적 계획법큰 정수(64비트)P0042

계단 오르기 방법 수

n칸짜리 계단을 맨 아래(0번째 칸)에서 꼭대기(n번째 칸)까지 오른다.
한 걸음에 한 칸 또는 두 칸을 오를 수 있다.
꼭대기에 정확히 닿는 서로 다른 걸음 순서의 수를 출력하라.
예를 들어 n = 3이면 1+1+1, 1+2, 2+1의 3가지이다.

입력: 1 ≤ n ≤ 70
출력: 방법의 수

예시 1 · stdin

stdout

예시 2 · stdin

stdout

20365011074

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이

마지막 걸음은 한 칸이거나 두 칸이니 ways[i] = ways[i-1] + ways[i-2]이고, 표를 0번 칸부터 채우면 n번만 더하면 돼요(동적 계획법).
같은 식을 재귀로 그대로 쓰면 같은 칸을 몇 번이고 다시 구해서 n = 70이면 부르기가 약 10^14번이라 끝나지 않아요 — 크레이콘은 실행 걸음이 약 5천만 번을 넘으면 멈춰요.
답은 n = 46에서 2,971,215,073으로 32비트 int(약 21억)를 넘으니 C·C++·Java·C#은 long/long long 표가 필요해요.
n = 70의 답 308,061,521,170,129는 2^53 안이라 JavaScript·TypeScript·크레이콘의 수로도 정확하고, Python은 끝이 없어요.
표 만들기: Python [0] * (n + 1), JavaScript new Array(n + 1).fill(0), Java·C# new long[n + 1], C++ std::vector<long long>(n + 1), 크레이콘 새목록(n + 1, 0).

Pythonmain.py · 7 줄

n = int(input())ways = [0] * (n + 1)  # ways[i] = i번째 칸까지 오르는 방법 수ways[0] = 1ways[1] = 1for i in range(2, n + 1):    ways[i] = ways[i - 1] + ways[i - 2]  # 마지막 걸음이 한 칸 또는 두 칸print(ways[n])

JavaScriptmain.js · 6 줄

const n = Number(require("fs").readFileSync(0, "utf8").trim());const ways = new Array(n + 1).fill(0); // ways[i] = i번째 칸까지 오르는 방법 수ways[0] = 1;ways[1] = 1;for (let i = 2; i <= n; i++) ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸console.log(ways[n]);

TypeScriptmain.ts · 7 줄

import { readFileSync } from "node:fs";const n: number = Number(readFileSync(0, "utf8").trim());const ways: number[] = new Array(n + 1).fill(0); // ways[i] = i번째 칸까지 오르는 방법 수ways[0] = 1;ways[1] = 1;for (let i = 2; i <= n; i++) ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸console.log(ways[n]);

JavaMain.java · 14 줄

import java.util.Scanner; public class Main {    public static void main(String[] args) {        int n = new Scanner(System.in).nextInt();        long[] ways = new long[n + 1]; // ways[i] = i번째 칸까지 오르는 방법 수        ways[0] = 1;        ways[1] = 1;        for (int i = 2; i <= n; i++) {            ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸        }        System.out.println(ways[n]);    }}

C#Main.cs · 17 줄

using System; class Program{    static void Main()    {        int n = int.Parse(Console.ReadLine().Trim());        long[] ways = new long[n + 1]; // ways[i] = i번째 칸까지 오르는 방법 수        ways[0] = 1;        ways[1] = 1;        for (int i = 2; i <= n; i++)        {            ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸        }        Console.WriteLine(ways[n]);    }}

C++main.cpp · 14 줄

#include <iostream>#include <vector> int main() {    int n;    std::cin >> n;    std::vector<long long> ways(n + 1); // ways[i] = i번째 칸까지 오르는 방법 수    ways[0] = 1;    ways[1] = 1;    for (int i = 2; i <= n; i++) {        ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸    }    std::cout << ways[n] << '\n';}

Cmain.c · 14 줄

#include <stdio.h> int main(void) {    int n;    scanf("%d", &n);    long long ways[71]; // ways[i] = i번째 칸까지 오르는 방법 수    ways[0] = 1;    ways[1] = 1;    for (int i = 2; i <= n; i++) {        ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸    }    printf("%lld\n", ways[n]);    return 0;}

Craykonmain.cray · 11 줄

n = 콘솔.줄읽기().수로변환();// ways[i] = i번째 칸까지 오르는 방법 수ways = 새목록(n + 1, 0);ways[0] = 1;ways[1] = 1;반복 (i = 2; i <= n; i++){    // 마지막 걸음이 한 칸 또는 두 칸    ways[i] = ways[i - 1] + ways[i - 2];}콘솔.쓰기(ways[n]);