목록DP (2)
나무 숲
파도반 수열 Padovan sequence 1, 1, 1, 2, 2, 3, 4, 5, 7, 9... 위 그림과 수열로 구성된 문제가 국내 ACM 문제 중 하나로 나왔었습니다. 그림, 수열을 참고하여 정수 n을 입력했을 때 n번째 값을 출력하는 내용입니다. 수열의 초기값과 점화식을 알고 있으면 아아아주 쉽게 풀 수 있지만 그림과 수열로 유추하실 수 있으면 더 좋겠습니다! 파도반 수열이란?? Richard Padovan에 의해 이름붙었습니다. 위 그림은 파도반 수열을 표현하는 그림 중 하나입니다. 각 삼각형은 한 변을 두 개의 다른 삼각형과 공유하는데요, 초기값 P(0)~P(2)를 제외하고 P(n) = P(n-2) + P(n-3)임을 알 수 있습니다. * 초기값이 P(0) = P(1) = P(2) = 1인 ..
셀프 넘버 * 넥슨 입사 문제 중 가장 쉬운 문제라고도 알려진 내용이라고 합니다. 1949년 인도 수학자 D.R. Kaprekar가 이름 붙인 셀프 넘버란? 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의할 때, n을 d(n)의 생성자(Generator)라고 한다. 생성자가 없는 숫자를 셀프 넘버라고 한다. n이 주어졌을 때, n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예시 - d(75) = 75+7+5 = 87 이므로 87은 셀프 넘버가 아니다. - 생성자가 한 개보다 많은 경우 : 101 d(91) = 91 + 9 + 1 = 101 d(100) = 100 + 1 = 101 저의 모자란 코드 문제 : 1~100까지의 숫..