해킹왕 양선규

끔찍한 DP 문제이다.문제를 고른 후에 알았는데 꽤 유명한 문제인 것 같다.말 그대로 계단 수의 개수를 구하는 문제다. 점화식을 찾으면 쉽게 풀 수 있지만 그것을 찾는 게 매우 어렵다. 처음 접근 방식은, 1, 2, 3 자리수 계단 수 개수를 세서 그 증가폭에 대한 규칙을 찾으려 했지만 실패했다. 이 문제를 쉽게 풀기 위해선 2차원 배열을 사용하는 것과, 끝나는 숫자를 기준으로 생각하면 좀 더 쉽다. 예를 들어, N번째 자리에 숫자 1이 오기 위해선 N-1번째 숫자가 반드시 0 또는 2여야 한다.즉, N-1번째에서 0으로 끝나는 숫자의 수와 2로 끝나는 숫자의 수를 합하면 N번째 자리에 1이 오는 계단수의 개수를 알 수가 있다. 표를 그려보면 좀 더 이해하기 쉽다.  행은 자릿수(N), 열은 끝나는 수이..

x = int(input()) d = [0] * (x + 2) d[1] = 1 d[2] = 2 for i in range(3, x + 1): d[i] = (d[i-1] + d[i-2]) % 15746 print(d[x]) 다이나믹 프로그래밍 문제이다. 점화식만 찾으면 아주 간단하게 해결할 수 있다. 계산값을 저장해둘 DP테이블(리스트 d)를 생성하고, 초기값을 넣어준다. d[1]엔 1길이의 수열에서 나올 수 있는 경우의 수의 개수, d[2]엔 2길이, d[x]엔 x길이의 수열에서 나올 수 있는 경우의 수의 개수가 들어간다. 타일 경우의 수를 구하는 것은 언뜻 답이 없어 보이지만, 규칙이 있다. 현재 값들에 1을 붙이고, 이전 값들에 00을 붙이면 그게 다음 값이 된다. 즉 N=4 일 때의 경우의 수를 구..

DP(Dynamic Programming, 동적 계획법) - 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 이용해, 다시 큰 문제를 해결할 때 사용한다. - DP는 특정 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰인다. - “큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고, 재활용” - DP라는 이름은 그냥 멋있어 보여서 지은 이름이다. DP를 쓰는 이유 - 일반적인 재귀방식도 DP와 유사하지만, 일반적인 재귀를 단순히 사용 시 “동일한 작은 문제가 반복”되어, 비효율적인 계산이 될 수 있다. ex) 피보나치 수열. 한번 한 계산을 또 하고 또 하고 반복한다. --->>> DP 방식으로 작은 문제의 결과를 저장해두고 “재사용”하면 매우 효율적으로 해결할 수 있다. --->>..