컴굥일지

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12914 문제 내용 한 번에 갈 수 있는 칸은 1칸 또는 2칸이다. n번째 칸까지 가려고 할 때, 도달하는 방법이 몇 개인지 구하면 된다. (단, 1234567로 나눈 나머지를 구할 것) 문제 풀이 문제를 보자마자 dp를 떠올렸다. 문제를 풀기 위해 n=5일 때까지의 가짓수를 모두 적어보았다. 위의 사진과 같이, n-1칸까지 뛰고, +1칸 가는 것 경우와 n-2칸까지 뛰고, +2칸 가는 경우로 나눌 수 있다. 코드 #include #include using namespace std; int solution(int n) { int dp[n+1]; dp[1]=1; dp[2]=2; for(int i=..