KimMinJun
Coding Note
KimMinJun
전체 방문자
오늘
어제
  • 분류 전체보기 (487)
    • ALGORITHM (11)
      • 정렬 (6)
      • 최단경로 (1)
      • 자료구조 (1)
      • 슬라이딩 윈도우 (1)
      • etc (2)
    • Git (5)
    • Web (24)
      • Vanilla JS (13)
      • TS (2)
      • React (7)
      • ETC (1)
    • React 공식문서 (번역, 공부) (11)
      • Quick Start (2)
      • Installation (0)
      • Describing the UI (9)
      • Adding Interactivity (0)
      • Managing State (0)
      • Escape Hatches (0)
    • Next.js 공식문서 (번역, 공부) (3)
      • Getting Started (2)
      • Building Your Application (1)
    • PS (432)
      • 백준 (187)
      • Programmers (105)
      • CodeUp (21)
      • STL (3)
      • 제코베 JS 100제 (50)
      • SWEA (0)
      • LeetCode (65)
    • IT (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 관리

공지사항

인기 글

태그

  • 다이나믹 프로그래밍
  • C++
  • 제코베 JS 100제
  • C
  • 그래프
  • 문자열
  • Level 1
  • 백준
  • 수학
  • 정렬
  • programmers
  • codeup
  • Level 2
  • Level1
  • tree
  • js
  • recursion
  • LeetCode
  • Level 0
  • string

최근 댓글

최근 글

hELLO · Designed By 정상우.
KimMinJun

Coding Note

PS/CodeUp

CodeUp / Recursion(재귀) / 3704번 / 계단 오르기2 / C++

2020. 9. 14. 13:53

문제 설명   

n개의 계단이 있다.

어떤 사람이 계단을 오르려 하는데 이 사람은 계단을 한번에 1계단 2계단 또는 3계단씩 오를 수 있다.

이 사람이 계단을 오를수 있는 경우의 수를 1000으로 나눈 나머지를 구하여라

 

입력

계단의 수 n이 입력된다. ( 1 <= n <= 100,000 )

 

출력

계단을 오를 수 있는 가지수에 1000으로 나눈 나머지를 출력한다.

 

입력 예시  

5

 

출력 예시

13

 

도움말

5=1+1+1+1+1

5=1+1+1+2

5=1+1+2+1

5=1+2+1+1

5=2+1+1+1

5=1+1+3

5=1+3+1

5=3+1+1

5=1+2+2

5=2+1+2

5=2+2+1

5=2+3

5=3+2

이렇게 총 13가지 경우가 존재한다.

 

#include <iostream>
using namespace std;

int arr[100001] = { 1,1,2 }; // 0번째를 1로 둘시, k가 3일때부터 재귀 성립.

int recursion(int k) {
	if (arr[k]) return arr[k];

	else {
		arr[k] = (recursion(k - 3) + recursion(k - 2) + recursion(k - 1)) % 1000;
	}

	return arr[k];
}

int main() {
	int k;
	cin >> k;

	cout << recursion(k) << endl;
}

이번 문제도 재귀를 활용할 수 있는 공식을 알아내는 것이 중요했다.

이런 문제가 있을시, 눈으로 짐작이 안되면 직접 손으로 써보면서 하는 것을 추천한다.

5일때 케이스는 문제에 있으니, 6일때 케이스까지 해서 공식을 알아내었다.

항상 느끼지만, 재귀안에 여러 재귀가 들어갈수록 메모이제이션을 해야 시간초과가 안나는 것 같다.

메모이제이션은 어려운 개념이 아니니 꼭 알고가면 유용하게 쓰일 것 같다.

저작자표시 (새창열림)

'PS > CodeUp' 카테고리의 다른 글

CodeUp / Recursion(재귀) / 4564번 / 계단 오르기 / C++  (0) 2020.09.17
CodeUp / Recursion(재귀) / 3733번 / 우박수 길이(3n + 1)(large) / C++  (0) 2020.09.14
CodeUp / Recursion(재귀) / 3702번 / 파스칼의 삼각형2 / C++  (0) 2020.09.13
CodeUp / Recursion(재귀) / 1930번 / SuperSum / C++  (0) 2020.09.13
    'PS/CodeUp' 카테고리의 다른 글
    • CodeUp / Recursion(재귀) / 4564번 / 계단 오르기 / C++
    • CodeUp / Recursion(재귀) / 3733번 / 우박수 길이(3n + 1)(large) / C++
    • CodeUp / Recursion(재귀) / 3702번 / 파스칼의 삼각형2 / C++
    • CodeUp / Recursion(재귀) / 1930번 / SuperSum / C++
    KimMinJun
    KimMinJun

    티스토리툴바