점화식4 [C/C++] 백준 11444: 피보나치 수 6 (점화식 풀이) https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 맨 처음에 다른 문제처럼 DP로 풀려고 했지만 너무 범위가 커 메모리초과가 나왔다. 구현!! 이 문제와 같이 입력의 수가 과도하게 크고 DP를 사용해야할 상황일 때 (1.)항상 점화식을 2개로 나눠서 풀 수 있도록 생각을 해야한다. 특히 (2.)한번 지난간 곳을 저장해둬서 한번 지난 곳은 다시 못 지나가게 만들어 시간을 줄여야할 필요도 있다. 1) 그래서 점화식을 나누기 위해 머리를 굴렸지만 결국 두개로 나누지 못했다. 사실 거의 다 오긴 했지만 마지막에... 그렇게 다른 .. 2023. 9. 17. [C/C++] 2193: 이친수 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이 문제 역시 2차원 배열 dp[][]을 이용하여 풀었다. dp[i][0]에는 길이가 i인 이친수 중 0으로 끝나는 수의 개수를 dp[i][1]에는 길이가 i인 이친수 중 1로 끝나는 수의 개수를 dp[i][2]에는 길이가 i인 이친수의 개수를 저장하였다. 이렇게 나눈 이유는 마지막이 0으로 끝나면 그 다음에는 0과 1 모두 올 수 있지만 1로 끝나게 된다면 그 다음에 0밖에 못온다. .. 2023. 8. 31. [C] 2579: 계단 오르기 이 문제도 역시 배열에 저장을 해가며 점화식을 구하기 위해 노력하였다. 먼저 각 계단마다 점수를 저장하는 score배열을 정의하고 각 단계마다 가장 높은 점수를 저장하는 arr배열을 정의하였다. 그리고 초기, 계단을 2개 오르기까지의 경우는 for문이 아닌 직접 배열에 저장하는 방식을 택했고 (어떤 방법으로 for문을 구성할지 감을 잡기위해서 & 초기값은 직접 정해줘야함) for문에서는 연속된 3개가 되는지에 따라 if문을, 그리고 각각의 if문에서 2계단을 뛰어넘는게 이득인지 1계단을 뛰어넘는게 이득인지 판별해 arr배열에 저장하였다. 그리고 이때 이차원 배열을 이용한 이유는 연속된 3개의 계단을 오른지 판별하기 위해서였다. 소스코드는 아래와 같다. #include int main(void) { int.. 2023. 7. 22. [C] 1463: 1로 만들기 맨 처음에는 아예 모든 배열에 미리 수를 찾는 과정으로 만들려고 했고 이때 아래 소스 코드와 같은 방법으로 구현하려고 했지만 시간초과가 떠서 실패하였다. #include #include int arr[2][1000001]; void memory(int arr[2][1000001],int n,int cnt) { if(n>1000000) return; if(arr[1][n*3]>cnt ||arr[1][n*3]==0) { arr[0][n*3]=cnt; arr[1][n*3]=cnt; memory(arr,n*3,cnt+1); } if(arr[1][n*2]>cnt || arr[1][n*2]==0) { arr[0][n*2]=cnt; arr[1][n*2]=cnt; memory(arr,n*2,cnt+1); } if(ar.. 2023. 7. 20. 이전 1 다음
