C C++166 C언어 백준 2193번 이친수 문제 풀이 이친수를 나열 해 보면 피보나치 수열과 동일한 패턴을 보이고 있기 때문에 피보나치 수열을 사용하여 문제를 풀이한다. 코드 #include int n; long long arr[100]={0,}; int sum; int main(void) { scanf("%d", &n); arr[0]=0; arr[1]=1; arr[2]=1; for(int i=3; i 2022. 6. 10. C언어 백준 11057번 오르막 수 문제 풀이 오르막 수는 수의 자리가 자릿수가 증가할 때 오르는 수이다. 규칙을 파악하여 점화식을 세워야하는 문제이다. 우선 DP 배열을 어떻게 구성할 지 생각 해 보자. DP[자릿수][숫자] = 개수 로 세울 수 있다. 몇 번째 자릿수인지, 해당 자릿수의 오는 숫자 0~9, 그리고 배열 안에 담긴 경우의 수가 몇 개인지이다. 아래 표에서 N-1번째와 N번째 자리만 보더라도 알 수 있다. N번째 자리에 올 수 있는 수는 N-1번째 자릿수보다 같거나 크면 가능하다. 따라서, 0이었다면 0~9가 올 수 있는 것이고, 이 경우의 수는 N-1번째 자릿수의 0~9에 해당하는 경우의 수를 모두 더하면 전체 값이 나온다. 즉, DP[N][0]=DP[N-1][0]+DP[N-1][1]+.....+DP[N-1][9]인 것을.. 2022. 6. 10. C언어 백준 10844번 쉬운 계단 수 문제 풀이 계단 수는 자리 차이마다 1의 차이를 가지고 있는 수이다. DP에서 중요한 점은 배열로 풀 때 - DP의 인덱스는 어떤 값을 넣을 것이고 - 그 배열 안에는 어떤 값이 들어갈 지 - 점화식을 어떻게 세울 것인지 인 것 같다. 이번 문제도 마찬가지로 인덱스 값을 어떤 값을 넣지와 배열 안의 값이 어떤 값이 들어갈 지가 중요하였다. DP[몇 번째 수][자릿수] = 총 개수 로 정의할 수 있다. 이 때, 바로 옆 숫자 대비 1씩 다르다. 왼쪽부터 n번째 자릿수는 n-1번째 자릿수 값+1과 n-1번째 자릿수 값-1의 개수에서 오기 때문에 둘을 더하면 된다. 예를 들어 3번째 자릿수 3인 경우, 2번째 숫자 2의 개수와 2번째 숫자 4의 개수를 더한 개수가 된다. 다만, 0과 9는 올 수 있는 경우가 .. 2022. 6. 9. C언어 백준 9095번 1, 2, 3 더하기 문제 풀이 귀납적으로 경우의 수를 나열하고, 나열된 숫자를 통해 점화식을 세웠습니다. 이 점화식을 메모이제이션을 통해 기록하였습니다. 하나씩 나열 해 본 결과 첫 번째 나열된 값 a[1] = 1; 두 번째 나열된 값 a[2] = 2; 세 번째 나열된 값 a[3] = 4; 네 번째 나열된 값 a[4] = 7;.... 시험 때는 정확성을 위해 다섯 번째 나열된 값까지 구했을 것으로 보입니다. 결과적으로 a[n]=a[n-1]+a[n-2]+a[n-3] (n>=4) 점화식을 얻었습니다. 코드 #include int n; int arr[1010]={0,}; int main(void) { int T; scanf("%d",&T); for (int i=0; i 2022. 6. 7. 이전 1 ··· 16 17 18 19 20 21 22 ··· 42 다음