알고리즘!/Dynamic Programming33 [C] 2748: 피보나치 수 2 그냥 피보나치 수열을 만들면 된다. 다만 범위가 int형을 벗어나기 때문에 long long int를 사용해야한다는 것만 주의하면 쉽게 풀 수 있다!! #include int long long fibo[91]; int main(void) { int n; scanf("%d",&n); fibo[0]=0; fibo[1]=1; fibo[2]=1; for(int i=3;i 2023. 7. 30. [C] 1149: RGB거리 전형적인 Dynamic Programming 문제인걸 알 수 있었는데 그 이유는 subproblem을 여러번 이용해야하기 때문에 이를 위해서 dp[]에 저장해서 이용해야했고 최솟값과 관련된 문제였기 때문이다. 이 문제는 i=1일때부터 하나하나씩 해보면 점화식을 구하는 것보다는 i=n일때부터 거꾸로 생각하는게 좀 더 떠올리는게 쉬웠던 것 같다. (2Xn 타일링2와 같이!) 그리고 빨강,초록,파랑 각각을 선택했을때 최선인 경우를 따로따로 저장하는 것이 각각 생각하지 않고 dp[i]일때 최선인 것을 저장하는 것보다 효율적이었는데 이는 똑같은 색깔을 두번 연속 선택하지 못한다면 그 다음에 최선인 경우를 빨리 찾기 위해서이다. #include int red[1001]; int green[1001]; int blu.. 2023. 7. 30. 11727: 2Xn 타일링 2 이 문제도 타일링 1문제와 같이 점화식만 찾으면 쉽게 풀 수 있다. dp[i-2]에서와 dp[i-1]에서 각각 길이가 2개짜리와 1개짜리를 더했을때 나오는 경우의 수를 구하여 점화식을 만들어보면 dp[i]=dp[i-1]+dp[i-2]+dp[i-2]가 된다. 점화식을 풀 때 dp[1]부터 하나하나 해보면서 구하는 것도 좋지만 dp[i]일때부터 생각해서 일반적인 해의 풀이를 구하는 것이 이 문제에서는 점화식을 더 찾기 쉬운 경우이다. i-1 덩어리와 i-2 덩어리가 있을 때 i짜리 덩어리를 만들기 위한 경우의 수를 구하면 된다. #include int dp[1001]; int main(void) { int n; scanf("%d",&n); dp[1]=1; dp[2]=3; dp[3]=dp[1]*dp[2]+dp.. 2023. 7. 29. [C] 11726: 2Xn 타일링 생각보다 쉽게 풀려서 깜짝 놀랐다 아무래도 평소에 조금 더 어려운 문제를 푸느라 상대적으로 쉽게 느껴졌나보다! 아무래도 점화식도 피보나치 수열과 같은 형태라 생각이 떠올리기 쉬웠고 점화식형태도 하나라서 직관적으로 보였다. 무엇보다 구현도 간단했는데 다만 주위해야할건 입력값이 1000개인데 피보나치 수열의 특성상 f(1000)은 int의 범위에서 벗어난다. 아마 long long int를 써도 벗어날 것 이다, 따라서 이때 생각났던 문제가 nCr, 조합 관련 문제였는데 이것도 n!이 n이 커질수록 기하급수적으로 커지기 때문에 n-i를 곱할때 i만큼 동시에 나눠져야 범위를 벗어나지 않는다. 이것도 마찬가지로 10007을 넘어갈 때마다 10007로 나눈 나머지를 dp[]에 넣어주면 된다. 다음은 아래 소스코드.. 2023. 7. 25. 이전 1 ··· 3 4 5 6 7 8 9 다음